From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Wed Feb 18 2004 - 09:04:37 PST
You are invited to attend...
************************************************************************
*****************************
WHO: Irit Dinur
AFFILIATION: University of California, Berkeley
TITLE: PCP Testers: Towards a combinatorial proof of the
PCP Theorem
WHEN: Thu 2/26/2004
WHERE: 113/1021 Research Lecture Room, Microsoft Research
TIME: 3:30PM to 5:00PM
HOST: Jennifer Chayes and Assaf Naor
************************************************************************
******************************
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.
BIO:
Irit Dinur is currently a Miller fellow in Computer Science at UC
Berkeley. She graduated from the school of computer science in Tel-Aviv
University with Muli Safra as her advisor.
_______________________________________________
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 : Wed Feb 18 2004 - 09:05:18 PST