Probabilistically checkable proofs

ABSTRACT

Can a proof be checked without reading it?

REFERENCES

• 1: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 2: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 3: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 4: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 5: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 6: Babai, L., Fortnow, L., Lund, C. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity 1, 1 (1991), 3--40.
• 7: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 8: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Wigderson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• 9: Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060631]
• 10: A. Cohen , A. Wigderson, Dispersers, deterministic amplification, and weak random sources, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.14-19, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63449]
• 11: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 12: Irit Dinur, The PCP theorem by gap amplification, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132553]
• 13: Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.155-164, October 17-19, 2004 [doi>10.1109/FOCS.2004.16]
• 14: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 15: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 16: Lance Fortnow , John Rompel , Michael Sipser, On the power of multi-prover interactive protocols, Theoretical Computer Science, v.134 n.2, p.545-557, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90251-8]
• 17: Garey, M.A., Johnson, D.S. Computers and Intractability. Freeman, 1979.
• 18: Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 19: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 20: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 21: Håstad, J. Clique is hard to approximate within n to the power 1-epsilon. Acta Mathemat. 182 (1999), 105--142.
• 22: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 23: R. Impagliazzo , D. Zuckerman, How to recycle random bits, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.248-253, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63486]
• 24: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.406, October 19-22, 1997
• 25: Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations. R. Miller, and J. Thatcher, eds.1972, 85--103.
• 26: Subhash Khot, Guest column: inapproximability results via Long Code based PCPs, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067318]
• 27: Levin, L.A. Universal search problems. Problemy Peredachi Informatsii, 9, 3 (1973), 265--266.
• 28: Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
• 29: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 30: Papadimitriou, C., Yannakakis, M. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43 (1991), 425--440.
• 31: Radhakrishnan, J., Sudan, M. On Dinur's proof of the PCP theorem. Bulletin (New Series) Amer. Math. Soc., 44, 1 (Jan. 2007), 19--61.
• 32: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 33: Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
• 34: Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 27, (1948), 379--423, 623--656.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations