Dana Moshkovitz: An Algebraic Parallel Petition Theorem

Friday, March 28, 2014 - 12:45pm to 3:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Dana Moshkovitz
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.