From: Paul Beame (beame@cs.washington.edu)
Date: Mon Feb 23 2004 - 16:48:46 PST
CSE Theory Seminar
TIME: Wednesday, Feb 25, 2:30-3:20PM
PLACE: CSE 203
SPEAKER: Irit Dinur
U.C. Berkeley
TITLE: PCP Testers: Towards a combinatorial proof of the PCP Theorem
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 a PCP-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, as opposed to the current proof in which one has to construct the two PCPs with respect to "compatible encoding" of their variables).
Based on this notion, we present two main results:
The first is a new proof of the PCP theorem. For this proof, we employ
composition of PCP-Testers, and a new combinatorial aggregation technique.
We achieve the final NP \subset PCP(logn,1) result relying only on a very
weak basic PCP, i.e. one where the verifier reads chunks of n^{1-\alpha}
bits. While this implies an arguably simpler proof of the PCP theorem,
we still rely (in the construction of that basic PCP) on some of the
algebraic components of the original proof (most notably, on low-degree tests).
Our second result overcomes this difficulty for a weaker variant of the
PCP-theorem (a variant which still implies very interesting hardness of
approximation results). Particularly, we give a purely combinatorial
standalone proof for NP \subset PCP[polylog n,1].
This talk is based on joint work with Omer Reingold.
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Mon Feb 23 2004 - 16:59:12 PST