Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR11-104 | 7th January 2013 15:30

Combinatorial PCPs with efficient verifiers

RSS-Feed




Revision #3
Authors: Or Meir
Accepted on: 7th January 2013 15:30
Downloads: 758
Keywords: 


Abstract:

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than a decade later, Dinur (J. ACM 54(3)) gave a simpler and arguably more intuitive proof using alternative combinatorial techniques.

One disadvantage of Dinur's proof compared to the previous algebraic proof is that it yields less efficient verifiers. In this work, we provide a combinatorial construction of PCPs with verifiers that are as efficient as the ones obtained by the algebraic methods. The result is the first combinatorial proof of the PCP theorem for NEXP (originally proved by Babai et al., FOCS 1990), and a combinatorial construction of super-fast PCPs of Proximity for NP (first constructed by Ben-Sasson et al., CCC 2005).



Changes to previous version:

Few more minor fixes.


Revision #2 to TR11-104 | 31st December 2012 17:37

Combinatorial PCPs with efficient verifiers





Revision #2
Authors: Or Meir
Accepted on: 31st December 2012 17:37
Downloads: 609
Keywords: 


Abstract:

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than a decade later, Dinur (J. ACM 54(3)) gave a simpler and arguably more intuitive proof using alternative combinatorial techniques.

One disadvantage of Dinur's proof compared to the previous algebraic proof is that it yields less efficient verifiers. In this work, we provide a combinatorial construction of PCPs with verifiers that are as efficient as the ones obtained by the algebraic methods. The result is the first combinatorial proof of the PCP theorem for NEXP (originally proved by Babai et al., FOCS 1990), and a combinatorial construction of super-fast PCPs of Proximity for NP (first constructed by Ben-Sasson et al., CCC 2005).



Changes to previous version:

Minor changes that improve the readability of some parts.


Revision #1 to TR11-104 | 3rd August 2011 21:57

Combinatorial PCPs with efficient verifiers





Revision #1
Authors: Or Meir
Accepted on: 3rd August 2011 21:57
Downloads: 901
Keywords: 


Abstract:

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than a decade later, Dinur (J. ACM 54(3)) gave a simpler and arguably more intuitive proof using alternative combinatorial techniques.

One disadvantage of Dinur's proof compared to the previous algebraic proof is that it yields less efficient verifiers. In this work, we provide a combinatorial construction of PCPs with verifiers that are as efficient as the ones obtained by the algebraic methods. The result is the first combinatorial proof of the PCP theorem for NEXP (originally proved by Babai et al., FOCS 1990), and a combinatorial construction of super-fast PCPs of Proximity for NP (first constructed by Ben-Sasson et al., CCC 2005).



Changes to previous version:

Fixed a bibtex compilation error.


Paper:

TR11-104 | 3rd August 2011 19:18

Combinatorial PCPs with efficient verifiers





TR11-104
Authors: Or Meir
Publication: 3rd August 2011 19:36
Downloads: 848
Keywords: 


Abstract:

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than a decade later, Dinur (J. ACM 54(3)) gave a simpler and arguably more intuitive proof using alternative combinatorial techniques.

One disadvantage of Dinur's proof compared to the previous algebraic proof is that it yields less efficient verifiers. In this work, we provide a combinatorial construction of PCPs with verifiers that are as efficient as the ones obtained by the algebraic methods. The result is the first combinatorial proof of the PCP theorem for NEXP (originally proved by Babai et al., FOCS 1990), and a combinatorial construction of super-fast PCPs of Proximity for NP (first constructed by Ben-Sasson et al., CCC 2005).



ISSN 1433-8092 | Imprint