From: Paul Beame (beame@cs.washington.edu)
Date: Wed Feb 25 2004 - 10:31:18 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 ``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.
_______________________________________________
_______________________________________________
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 : Wed Feb 25 2004 - 10:31:48 PST