Summary: The current proof of the Probabilistically Checkable Proofs (PCP) theorem (i.e., \({\mathcal NP}={\mathcal 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 S. Arora and S. Safra [(*) J. ACM 45, No. 1, 70-122 (1998; Zbl 0903.68076)] and S. Arora, C. Lund. R. Motwani, M. Sudan and M. Szegedy [(**) Proof verification and hardness of approximation problems. 33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24-27, 1992. Washington, DC: IEEE Computer Society Press, 14-23 (1992)].
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 in (*) and (**) by a combinatorial lemma (which does not refer to low-degree tests or polynomials).