Comment by nyrikki

I haven't done a real review yet, but skimming it seems to relate to Arthur-Merlin[0] oracles and public fair coins.

If you view random numbers as normal numbers, they will seem to be algorithmically random, or at least exceed the complexity of any proof, or even practical proof.

Basically the work of Chatlin, where given the kolmogorov complexity of your verifier, you only have a limited number of bits in any L that you can prove anything.

Probably simpler to think about the challenges of proving a fair coins is fair.

They just have to produce an unfair coin that looks fair as a flawed analogy.

Fiat-Shamir depends on interactive proofs, which equals PSPACE, which seems huge, but it can be a hay in the haystack, and if you are using a magnet to reach into the haystack you will almost never pull out a piece of hay.

They are basically choosing the magnet for you.

[0] https://complexityzoo.net/Complexity_Zoo:A#am