Computer Science/Discrete Mathematics Seminar II

The PCP Theorem shows that any mathematical proof can be efficiently converted into a form that can be checked probabilistically by making only *two* queries to the proof, and performing a "projection test" on the answers. This means that the answer to the first query determines at most one satisfying answer to the second query. If the proof is correct, the checking algorithm always accepts. On the other, the probability that the checking algorithm accepts a proof for an invalid statement (this is the "error" of the check), is small. The PCP theorem, especially in the "projection" formulation described above, is extremely useful for proving NP-hardness of approximation results. Parallel Repetition gives error epsilon, for any given *constant* epsilon > 0. We show a construction that gives error epsilon that tends to 0 with n, the length of the proof. (Based on joint work with Ran Raz)