ECCC-Report TR96-047https://eccc.weizmann.ac.il/report/1996/047Comments and Revisions published for TR96-047en-usSun, 20 Oct 1996 00:00:00 +0200
Revision 1
| A Combinatorial Consistency Lemma with application to the PCP Theorem Revision of: TR96-047 |
Oded Goldreich,
Muli Safra
https://eccc.weizmann.ac.il/report/1996/047#revision1
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 get rid of low-degree tests altogether,
using our results it is now possible to prove the PCP Theorem
using a simple analysis of low-degree tests (which yields weaker bounds).
In other words, we replace the complicated algebraic analysis
of low-degree tests presented by Arora and Safra and Arora~et.~al.
by an intuitive combinatorial lemma
(which does not refer to low-degree tests or polynomials).
Sun, 20 Oct 1996 00:00:00 +0200https://eccc.weizmann.ac.il/report/1996/047#revision1
Paper TR96-047
| A Combinatorial Consistency Lemma with application to the PCP Theorem |
Oded Goldreich,
Muli Safra
https://eccc.weizmann.ac.il/report/1996/047
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 get rid of low-degree tests altogether,
using our results it is now possible to prove the PCP Theorem
using a simple analysis of low-degree tests (which yields weaker bounds).
In other words, we replace the complicated algebraic analysis
of low-degree tests presented by Arora and Safra and Arora~et.~al.
by an intuitive combinatorial lemma
(which does not refer to low-degree tests or polynomials).
Tue, 03 Sep 1996 09:36:13 +0300https://eccc.weizmann.ac.il/report/1996/047