Hardness of Projection Games

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Hardness of Projection Games
Speaker:Dana Moshkovitz
Affiliation:Member, School of Mathematics
Date:Tuesday, October 20
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/projectiongames

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)