A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

This is the authors' abstract. We don't add key points for this paper.

The current proof of the probabilistically checkable proofs (PCP) theorem (i.e., NP= PCP(log,O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the difficulty of obtaining strong results regarding low-degree tests; namely, results of the type obtained and used by Arora and Safra [J. ACM, 45 (1998), pp. 70--122] and Arora et al. [J. ACM, 45 (1998), pp. 501--555]. In this paper, we eliminate the need to obtain such strong results on low-degree tests when proving the PCP theorem. Although we do not remove the need for low-degree tests altogether, using our results it is now possible to prove the PCP theorem using a simpler analysis of low-degree tests (which yields weaker bounds). In other words, we replace the strong algebraic analysis of low-degree tests presented by Arora and Safra and Arora et al. by a combinatorial lemma (which does not refer to low-degree tests or polynomials).