On Interactive Proofs of Proximity with Proof-Oblivious Queries
summary
Authors Oded Goldreich, Guy N. Rothblum and Tal Skverer show a concrete exponential separation between property testing and interactive proofs of proximity under a prover-oblivious queries hierarchy. They use the specific uuvv property, cite the Alon–Krivelevich–Newman–Szegedy lower bound of Omega(sqrt n) queries for testers, and build a 3 messages pre-coordinated protocol that uses O(1) queries and O(log n) communication to verify proximity. They also map the hierarchy: isolated models collapse to testing, general prover-oblivious needs only two messages for a gap.
AI-written summary · about
chapters (13)
- 0:00Interactive proofs of proximity intro
- 1:25Basics of interactive proofs of proximity
- 3:12IPP vs property testing gap
- 5:42Prover-oblivious queries
- 7:29Verifier decomposition
- 8:55Hierarchy models
- 11:07Exponential gap in pre-coordinated
- 12:15Property definition
- 15:27Pre-coordinated protocol
- 17:57Why protocol works
- 20:52Summary of gap results
- 21:16Comparing prover-oblivious models
- 23:03Conclusions and limits
related talks
42mQuantum program analysis: Verification and Testing
01h 02mTesting Boolean Functions
16mProjection-Based Runtime Assertions for Testing and Debugging Quantum Programs
19mNon-Termination Proving at Scale
32mTheory, Design, and Implementation of Projection-based Assertions for Quantum Debugging
20mTruly Stateless, Optimal Dynamic Partial Order Reduction
18mPreview: Verification (Correctness)
34mWeak Versions of Extended Resolution