link

November 23, Tuesday
12:00 – 14:00

New PCP Testers: Towards a combinatorial proof of the PCP Theorem
Computer Science seminar
Lecturer : Dr. Irit Dinur
Lecturer homepage : http://www.cs.huji.ac.il/~dinuri/
Affiliation : Hebrew University, CS department
Location : -101/58
Host : Dr. Kobbi Nissim
In this talk I will describe (briefly) what the PCP theorem is, and then describe recent work in which we look back into the proof of the PCP theorem, with the goal of finding new proofs that are "more combinatorial" and arguably simpler. For that we introduce the notion of assignment tester. This natural object is a strengthening of the standard PCP verifier, and enables simpler composition that is truly modular (i.e. one can compose two testers without any assumptions on how they are constructed). A related notion was independently introduced by Ben-Sasson et. al. Based on this notion, we present two main results:

1. The first is a new proof of the PCP theorem. This proof relies on a rather weak PCP given as a "black box". From this, we construct combinatorially the full PCP, relying on composition and a new combinatorial aggregation technique.

2. Our second construction is a "standalone" combinatorial construction showing NP in PCP [polylog, 1]. This implies, for example, that max-SAT is quasi-NP-hard

Based on joint work with Omer Reingold.