Abstract:

In this work we look back into the proof of the PCP theorem, with the goal
of finding new proofs that are either simpler or "more combinatorial". 
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). 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 subset PCP[polylog, 1]. This implies, for example, that max-SAT
is quasi-NP-hard.

Joint work with Irit Dinur