An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing
summary
Proposes repeating the low‑degree (line vs line) test in parallel to turn a base soundness of about 1/|F| into error roughly 1/|F|^k, and proves this by analyzing incidence graphs of surfaces vs k‑tuples using a graph product that preserves mixing. Achieves exponential soundness in k at the cost of randomness growing from m log |F| to about m^2 log |F|, and requires a third prover (a middle verifier) to block trivial cheating. Leaves derandomization to reach the Sliding Scale Conjecture as an open problem.
AI-written summary · about
chapters (18)
- 0:00Start
- 1:01The Sliding Scale Conjecture Bellare, Goldwasser, Lund, Russell '93
- 8:56Implications to Hardness of Approximation
- 11:04History of Low Error
- 17:20How To Get Low Error?
- 20:47Line vs. Line Test
- 32:58Curve vs. Curve Test
- 36:05More generally: Surface vs. Surface Test
- 36:15Problem: Provers Can Use Large Intersection To Cheat!
- 39:55IKW Solution: Add Third Prover
- 42:46Parallel Repetition for Low Degree Tests
- 45:16About Our Parallel Repetition Proof
- 47:32Surface vs. Points Incidence Graph
- 49:58Identifying a Strategy
- 51:58Mixing Parameters
- 53:15Incidence Graphs As Product Graphs
- 55:45Derandomized parallel repetition?
- 58:07Challenge Problem: Intersecting Surfaces
related talks
35mLow-Overhead Fault Tolerance in Two Dimensions
32mTowards local testability for quantum coding
01h 37mFault-Tolerance Against Adversarial Errors & PCPs
18mStatistical Testing of Quantum Programs via Fixed-Point Amplitude Amplification
53mFrom randomized benchmarking to cycle error reconstruction
22mLower Bounds on Stabilizer Rank
20mDistributed Quantum Proofs for Replicated Data
20mUnitary property testing lower bounds by polynomials