The current proof of the probabilistically checkable proofs (PCP) theorem (
i.e., NP = PCP (log, O(1))) is very complicated. One source of difficulty i
s the technically involved analysis of low-degree tests. Here, we refer to
the difficulty of obtaining strong results regarding low-degree tests; name
ly, results of the type obtained and used by Arora and Safra [J. ACM, 45 (1
998), 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-d
egree tests when proving the PCP theorem. Although we do not remove the nee
d 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 y
ields weaker bounds). In other words, we replace the strong algebraic analy
sis 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 polynomial
s).