A combinatorial consistency lemma
with application to proving the PCP Theorem
Webpage for a paper by Oded Goldreich and Muli Safra
Abstract
The current proof of the 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 and Arora et. al.
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).
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.