From: Rosa Teorell (rosat@microsoft.com)
Date: Thu Feb 26 2004 - 07:24:44 PST
Please note abstract has been updated.
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-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 ``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.
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 : Thu Feb 26 2004 - 07:25:11 PST