Abstract

he Sliding Scale Conjecture in PCP states that NP has multi-prover protocols with a constant number of provers and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in classical multi-prover protocols, and it implies hardness of approximation up to polynomial factors for problems like Max-CSP (with polynomial-sized alphabet), Directed-Sparsest-Cut and Directed-Multi-Cut.

In this work we prove:

  1. The Sliding Scale Conjecture follows from a construction of a low degree test whose soundness error is exponentially small in the randomness of the verifier.
  2. A parallel repetition theorem for low degree testing that decreases the error probability of a low degree test exponentially.
  3. Applying the parallel repetition theorem on an existing low degree test, we get the low degree test with the smallest error known to date.

The missing piece for proving the Sliding Scale Conjecture is a derandomization of the parallel repetition theorem. This seems plausible given the algebraic structure of the low degree testing problem, which was utilized for derandomization in the past.

Video Recording