Dana Moshkovitz: An Algebraic Parallel Petition Theorem

A long line of work in Theoretical Computer Science shows that a function is close to a low degree polynomial iff it is close to a low degree polynomial "locally". This is known as "low degree testing", and is the core of the algebraic approach to construction of PCP.

 

We prove a parallel repetition theorem for low degree testing achieving optimal exponential decay of the error probability. We instantiate this theorem to obtain a low degree tester whose error probability is much smaller than any known local tester. A key lemma is an analysis of the sampling properties of the incidence graph of degree-k curves and k'-tuples of points in a finite space F^m.

 

We show that the Sliding Scale Conjecture in PCP, namely the conjecture that there are PCP verifiers whose error is exponentially small in their randomness, would follow from a derandomization of our parallel repetition theorem.