loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
ASCII Text
x 
 
Irit Dinur, Omer Reingold, "Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem," Foundations of Computer Science, IEEE Annual Symposium on, pp. 155-164, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.16,
author = {Irit Dinur and Omer Reingold},
title = {Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {155-164},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.16},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem
SN - 0272-5428
SP155
EP164
A1 - Irit Dinur,
A1 - Omer Reingold,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Irit Dinur, University of California at Berkeley
Omer Reingold, Weizmann Institute

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 an assignment tester, which is a strengthening of the standard PCP verifier, in the following sense. Given a statement and an alleged proof for it, while the PCP verifier checks correctness of the statement, the assignment-tester checks correctness of the statement and the proof. This notion enables composition that is truly modular, i.e., one can compose two assignment-testers without any assumptions on how they are constructed. A related notion was independently introduced in [Ben-Sasson et. al. STOC 04].

We provide a toolkit of (non-trivial) generic transformations on assignment testers. These transformations may be interesting in their own right, and allow us to present the following two main results:

  • 1. The first is a new proof of the PCP Theorem. This proof relies on a rather weak assignment tester given as a "black box". From this, we construct combinatorially the full PCP. An important component of this proof is a new combinatorial aggregation technique (i.e., a new transformation that allows the verifier to read fewer, though possibly longer, "pieces" of the proof). An implementation of the black-box tester can be obtained from the algebraic proof techniques that already appear in [4, 10]. Obtaining a combinatorial implementation of this tester would give a purely combinatorial proof for the PCP theorem, which we view as an interesting open problem.
  • 2. Our second construction is a "standalone" combinatorial construction showing NP ⊆ PCP[polylog, 1]. This implies, for example, that approximating max-SAT is quasi-NP-hard. This construction relies on a transformation that makes an assignment tester "oblivious": so that the proof locations read are independent of the statement that is being proven. This eliminates, in a rather surprising manner, the need for aggregation in a crucial point in the proof.

    • Citation:
    Irit Dinur, Omer Reingold, "Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem," focs, pp.155-164, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.