__
Revision #1 to TR96-047 | 20th October 1996 00:00
__
#### A Combinatorial Consistency Lemma with application to the PCP Theorem Revision of: TR96-047

**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 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).

__
TR96-047 | 2nd September 1996 00:00
__

#### A Combinatorial Consistency Lemma with application to the PCP Theorem

**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 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).