Hardness of Projection Games

 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)