Pseudorandomness against AM circuits and new oracle separations

Value of the Information & Strength of the Argument

The value of the information is substantial for the theoretical computer science community, as it provides new oracle separations that advance the understanding of quantum versus classical interactive proof systems. The argumentation is solid: the speaker carefully derives the equivalence between IP protocols and average-max circuits, then proves a pseudorandomness theorem for those circuits. The proof outline is rigorous, with key technical steps (smoothing, covariance bounds) clearly explained. The speaker also addresses clarifying questions, which reinforces the depth of the argument. The novel contribution is significant, as it had not been known before that such a separation holds, and the pseudorandomness result against AM circuits is a standalone contribution.

Scientific Rigor, Source Quality, Title Accuracy

The talk demonstrates high scientific rigor, referencing prior work (Mahadev, McKague, Reichardt et al., Aaronson, etc.) and building on the IP=PSPACE theorem. The quality of sources is high, as all cited works are well-known in the field. The title accurately reflects the content: the talk indeed focuses on pseudorandomness against AM circuits and proves new oracle separations. The description link to the Simons Institute provides access to the talk page, which is a reliable institutional source. No discrepancies were found between the title and the content.

8/10

The talk presents new research results in computational complexity theory, delivered at the Simons Institute by a researcher from UC Berkeley. The content is rigorous, built on established theorems (IP=PSPACE, etc.) and recent works. The speaker engages with audience questions and provides proof sketches, indicating high technical accuracy.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 02:00Introduction of the central question: can a quantum prover efficiently convince a classical verifier?
• 05:00Review of known results: BQP⊆PSPACE, IP=PSPACE, Mahadev's protocol, multi-prover works.
• 10:00Construction of the oracle separation: BQP not in IP relative to an oracle, and IP vs MIP separation.
• 15:00Definition of the forrelation distribution, with Gaussian sampling and Hadamard transform.
• 20:00Quantum algorithm that distinguishes forrelation from uniform with constant advantage.
• 25:00Reduction of IP protocols to average-max circuits, including the structural transformation.
• 30:00Key observation: average-max circuits are convex, crucial for the analysis.
• 35:00Statement of the pseudorandomness result: forrelation is pseudorandom against AM circuits.
• 40:00Proof outline: smoothing with Gaussian noise and hybrid argument.

• Talk page at Simons Institute — Official page for the talk, containing abstract and possibly slides.