Madhu Sudan
Supplemental Material
Available for Download
PowerPoint presentation by Madhu Sudan
Presentation by Madhu Sudan
- Arora, S., Babai, L., Stern, J., Sweedyk, Z. The hardness of approximate optima in lattices, codes and systems of linear equations. J. Comput. Syst. Sci. 54, 2 (Apr. 1997), 317--331. Google Scholar
Digital Library
- Arora, S., Lund, C. Hardness of approximations. Approximation Algorithms for NP-Hard Problems. D.S. Hochbaum, ed. PWS, 1995. Google ScholarDigital Library
- Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May 1998), 501--555. Google ScholarDigital Library
- Arora, S., Safra, S. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1 (Jan. 1998), 70--122. Google ScholarDigital Library
- Babai, L., Fortnow, L., Levin, L.A., Szegedy, M. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on the Theory of Computing (New York, 1991), ACM, 21--32. Google ScholarDigital Library
- Babai, L., Fortnow, L., Lund, C. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity 1, 1 (1991), 3--40.Google ScholarCross Ref
- Babai, L., Moran, S. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity class. J. Comput. Syst. Sci. 36, 2 (Apr. 1988), 254--276. Google ScholarDigital Library
- Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A. Multi-prover interactive proofs: How to remove intractability. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing (1988), 113--131. Google ScholarDigital Library
- Ben-Sasson, E., Sudan, M. Short PCPs with poly-log rate and query complexity. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (New York, 2005), ACM, 266--275. Google ScholarDigital Library
- Cohen, A., Wigderson, A. Dispersers, deterministic amplification, and weak random sources (extended abstract). In IEEE Symposium on Foundations of Computer Science (1989), 14--19. Google ScholarDigital Library
- Cook, S.A. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium Theory of Computing (Ohio, 1971), Shaker Heights, 151--158. Google ScholarDigital Library
- Dinur, I. The PCP theorem by gap amplification. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (New York, 2006), ACM, 241--250. Preliminary version appeared as an ECCC Technical Report TR05-046. Google ScholarDigital Library
- Dinur, I., Reingold, O. Assignment testers: Towards a combinatorial proof of the PCP-theorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (Loc Alamitos, CA, USA, 2004), IE, 155--164. Google ScholarDigital Library
- Feige, U. A threshold of ln n for approximating set cover. J. ACM 45, 4 (1998), 634--652. Google ScholarDigital Library
- Feige, U., Goldwasser, S., Lov´sz, L., Safra, S., Szegedy, M. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2 (1996), 268--292. Google ScholarDigital Library
- Fortnow, L., Rompel, J., Sipser, M. On the power of multi-prover interactive protocols. Theor. Comput. Sci. 134, 2 (1994), 545--557. Google ScholarDigital Library
- Garey, M.A., Johnson, D.S. Computers and Intractability. Freeman, 1979.Google ScholarDigital Library
- Goldreich, O. Modern Cryptography, Probabilistic Proofs and Pseudorandomness, volume 17 of Algorithms and Combinatorics. Springer-Verlag, 1998. Google ScholarDigital Library
- Goldreich, O., Micali, S., Wigderson, A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 1 (July 1991), 691--729. Preliminary version in IEEE FOCS, 1986. Google ScholarDigital Library
- Goldwasser, S., Micali, S., Rackoff, C. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (February 1989), 186--208. Google ScholarDigital Library
- Håstad, J. Clique is hard to approximate within n to the power 1-epsilon. Acta Mathemat. 182 (1999), 105--142.Google ScholarCross Ref
- Håstad, J. Some optimal inapproximability results. J. ACM 48 (2001),798--859. Google ScholarDigital Library
- Impagliazzo, R., Zuckerman, D. How to recycle random bits. In IEEE Symposium on Foundations of Computer Science (1989), 248--253. Google ScholarDigital Library
- Karloff, H., Zwick, U. A 7/8-approximation algorithm for max 3sat? In FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97) (Washington, DC, USA, 1997), IEEE Computer Society, 406--415. Google ScholarDigital Library
- Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations. R. Miller, and J. Thatcher, eds.1972, 85--103.Google Scholar
- Khot, S. Guest column: Inapproximability results via long code based PCPs. SIGACT News 36, 2, 25--42, 2005. Google ScholarDigital Library
- Levin, L.A. Universal search problems. Problemy Peredachi Informatsii, 9, 3 (1973), 265--266.Google Scholar
- Lund, C., Fortnow, L., Karloff, H.J., Nisan, N. Algebraic methods for interactive proof systems. J. ACM 39, 4 (Oct. 1992), 859--868. Google ScholarDigital Library
- Lund, C., Yannakakis, M. On the hardness of approximating minimization problems. J. ACM 41, 5 (Sept. 1994), 960--981. Google ScholarDigital Library
- Papadimitriou, C., Yannakakis, M. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43 (1991), 425--440.Google ScholarCross Ref
- Radhakrishnan, J., Sudan, M. On Dinur's proof of the PCP theorem. Bulletin (New Series) Amer. Math. Soc., 44, 1 (Jan. 2007), 19--61.Google Scholar
- Raz, R. A parallel repetition theorem. SIAM J. Comput. 27, 3 (1998), 763--803. Google ScholarDigital Library
- Shamir, A. IP = PSPACE. J. ACM 39, 4 (Oct. 1992), 869--877. Google ScholarDigital Library
- Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 27, (1948), 379--423, 623--656.Google ScholarCross Ref
Index Terms
- Probabilistically checkable proofs
Recommendations
Probabilistically Checkable Proofs Over the Reals
Probabilistically checkable proofs (PCPs) have turned out to be of great importance in complexity theory. On the one hand side they provide a new characterization of the complexity class NP, on the other hand they show a deep connection to approximation ...
Fast approximate probabilistically checkable proofs
We investigate the question of when a verifier, with the aid of a proof, can reliably compute a function faster than it can without the proof. The proof system model that we use is based on a variant of the Probabilistically Checkable Proofs (PCP) model,...
On the concrete efficiency of probabilistically-checkable proofs
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingProbabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables fast verification of long computations in many cryptographic constructions. Yet, despite the wonderful asymptotic savings they bring, PCPs are also the infamous ...
Reviews
Arturo Ortiz-Tapia
If a mathematical proof can be lengthy, verifying its validity may turn out to be almost as complex. Sudan offers a brief review of an alternative procedure to analyze mathematical proofs, using probabilistic algorithms. His explanation focuses specifically on the complexity of the query and the probability gap of certainty for accepting or rejecting a proof as a valid one. The article touches on the question of whether a proof can be checked efficiently, in polynomial time in the length of its shortest proof, and also if such a proof-mathematical or any other formal abstraction-can be queried about its validity, in probabilistic fashion, with the least possible questions. The article makes some progress toward answering such questions, although a probabilistic verifying algorithm that is of real practical use for mathematicians is still to be worked out. The topic of probabilistic checkable proofs is indeed important, and Sudan's article and the references therein should be studied by any pure mathematician who is working on provability. I would also recommend this paper to computer scientists who are dealing with problems related to proving the internal coherence of systems, especially if they are dependent on some form of combinatorial optimization. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments