More Web Proxy on the site http://driver.im/

Article

The PCP theorem by gap amplification

Author:

Irit DinurAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 241 - 250

https://doi.org/10.1145/1132516.1132553

Published: 21 May 2006 Publication History

Abstract

We present a new proof of the PCP theorem that is based on a combinatorial amplification lemma. The unsat value of a set of constraints C = (c₁,...,c_n), denoted UNSAT(C), is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables.We describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. The amplification step causes an increase in alphabet-size that is corrected by a PCP composition step. Iterative application of these two steps yields a proof for the PCP theorem.The amplification lemma relies on a new notion of "graph powering" that can be applied to systems of constraints. This powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander.We also apply the amplification lemma to construct PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. Namely, we prove SAT ∈ PCP_1/2,1[log₂(n • poly log n),O(1)].

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. J. ACM, 45(3):501--555, 1998.]]

Digital Library

[2]

S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70--122, 1998.]]

Digital Library

[3]

E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. Robust PCPs of proximity, shorter PCPs and applications to coding. In Proc. 36th ACM Symp. on Theory of Computing, 2004.]]

Digital Library

[4]

E. Ben-Sasson and M. Sudan. Robust PCPs of proximity, shorter PCPs and applications to coding. In Proc. 37th ACM Symp. on Theory of Computing, 2005.]]

Digital Library

[5]

E. Ben-Sasson, M. Sudan, S. P. Vadhan, and A. Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th ACM Symp. on Theory of Computing, pages 612--621, 2003.]]

Digital Library

[6]

A. Bogdanov. Gap amplification fails below 1/2. Comment on ECCC TR05-046, 2005.]]

[7]

I. Dinur and O. Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), 2004.]]

Digital Library

[8]

U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. Journal of the ACM, 43(2):268--292, 1996.]]

Digital Library

[9]

U. Feige and J. Kilian. Impossibility results for recycling random bits in two-prover proof systems. In Proc. 27th ACM Symp. on Theory of Computing, pages 457--468, 1995.]]

Digital Library

[10]

O. Goldreich and S. Safra. A combinatorial consistency lemma with application to proving the PCP theorem. In RANDOM. LNCS, 1997.]]

Digital Library

[11]

O. Goldreich and M. Sudan. Locally testable codes and PCPs of almost-linear length. In Proc. 43rd IEEE Symp. on Foundations of Computer Science, pages 13--22, 2002.]]

Digital Library

[12]

P. Harsha and M. Sudan. Small PCPs with low query complexity. In STACS, pages 327--338, 2001.]]

Digital Library

[13]

N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course: http://www.math.ias.edu/~boaz/ExpanderCourse/, 2003.]]

[14]

C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425--440, 1991.]]

[15]

A. Polishchuk and D. Spielman. Nearly linear size holographic proofs. In Proc. 26th ACM Symp. on Theory of Computing, pages 194--203, 1994.]]

Digital Library

[16]

J. Radhakrishnan. Private communication. 2005.]]

[17]

R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763--803, June 1998.]]

Digital Library

[18]

O. Reingold. Undirected st-connectivity in log-space. In Proc. 37th ACM Symp. on Theory of Computing, 2005.]]

Digital Library

[19]

O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Annals of Mathematics, 155(1):157--187, 2002.]]

[20]

M. Sipser and D. A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710--1722, 1996. Codes and complexity.]]

Cited By

Weiss M(2022)Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage ResilienceEntropy10.3390/e2407097024:7(970)Online publication date: 13-Jul-2022
https://doi.org/10.3390/e24070970
Hazay CVenkitasubramaniam MWeiss M(2022)ZK-PCPs from Leakage-Resilient Secret SharingJournal of Cryptology10.1007/s00145-022-09433-335:4Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00145-022-09433-3
Khot SMinzer DSafra MHatami HMcKenzie PKing V(2017)On independent sets, 2-to-2 games, and Grassmann graphsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055432(576-589)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055432
Show More Cited By

Index Terms

The PCP theorem by gap amplification
1. Theory of computation

Recommendations

The PCP theorem by gap amplification

The PCP theorem [Arora and Safra 1998; Arora et. al. 1998] says that every language in NP has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. The celebrated equivalence of this theorem and ...
The detectability lemma and quantum gap amplification
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

The quantum analogue of the constraint satisfaction problem is the fundamental physics question of finding the minimal energy state of a local Hamiltonian --- each term of the Hamiltonian specifies a local constraint whose violation contributes to the ...
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
661
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)6

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weiss M(2022)Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage ResilienceEntropy10.3390/e2407097024:7(970)Online publication date: 13-Jul-2022
https://doi.org/10.3390/e24070970
Hazay CVenkitasubramaniam MWeiss M(2022)ZK-PCPs from Leakage-Resilient Secret SharingJournal of Cryptology10.1007/s00145-022-09433-335:4Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00145-022-09433-3
Khot SMinzer DSafra MHatami HMcKenzie PKing V(2017)On independent sets, 2-to-2 games, and Grassmann graphsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055432(576-589)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055432
Aharonov DEldar L(2015)The commuting local Hamiltonian problem on locally expanding graphs is approximable in $$\mathsf{{NP}}$$NPQuantum Information Processing10.1007/s11128-014-0877-914:1(83-101)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s11128-014-0877-9
Ishai YWeiss MYang G(2015)Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient CircuitsTheory of Cryptography10.1007/978-3-662-49099-0_1(3-32)Online publication date: 24-Dec-2015
https://doi.org/10.1007/978-3-662-49099-0_1
Barenboim LElkin M(2014)Combinatorial algorithms for distributed graph coloringDistributed Computing10.1007/s00446-013-0203-227:2(79-93)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s00446-013-0203-2
Ishai YWeiss M(2014)Probabilistically Checkable Proofs of Proximity with Zero-KnowledgeTheory of Cryptography10.1007/978-3-642-54242-8_6(121-145)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54242-8_6
Vyalyi M(2013)Cones of multipowers and combinatorial optimization problemsComputational Mathematics and Mathematical Physics10.1134/S096554251305014X53:5(647-654)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1134/S096554251305014X
Moore CMertens S(2013)Mathematical ToolsThe Nature of Computation10.1093/acprof:oso/9780199233212.005.0001(911-943)Online publication date: 17-Dec-2013
https://doi.org/10.1093/acprof:oso/9780199233212.005.0001
Moore CMertens SMoore CMertens S(2013)Quantum ComputationThe Nature of Computation10.1093/acprof:oso/9780199233212.003.0015(819-910)Online publication date: 17-Dec-2013
https://doi.org/10.1093/acprof:oso/9780199233212.003.0015
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents