Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic

General Terms: Algorithms, Theory, Verification

Additional Key Words and Phrases: Approximation algorithms, complexity hierarchies, computations on polynomials and finite fields, error-correcting codes, hardness of approximations, interactive computation, NP-completeness, probabilistic computation, proof checking, reducibility and completeness, trade-offs/relations among complexity measures

Selected papers that cite this one

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998.

Selected references

• Miklós Ajtai, János Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132-140, New York City, 25-27 May 1987.

• Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optimia in lattices, codes, and systems of linear equations. In 34th Annual Symposium on Foundations of Computer Science, pages 724-733, Palo Alto, California, 3-5 November 1993. IEEE.

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 485-495, El Paso, Texas, 4-6 May 1997.

• László Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 421-429, Providence, Rhode Island, 6-8 May 1985.

• László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991.

• László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 21-31, New Orleans, Louisiana, 6-8 May 1991.

• M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 294-304, San Diego, California, 16-18 May 1993.

• Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs and non-approximability -- towards tight results. In 36th Annual Symposium on Foundations of Computer Science, pages 422-431, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 184-193, Montréal, Québec, Canada, 23-25 May 1994.

• Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 113-131, Chicago, Illinois, 2-4 May 1988.

• Manuel Blum and Sampath Kannan. Designing programs that check their work. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 86-97, Seattle, Washington, 15-17 May 1989.

• Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 73-83, Baltimore, Maryland, 14-16 May 1990.

• Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39, August 1994.

• Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96-106, March 1989.

• Anne Condon. The complexity of the max word problem and the power of one-way interactive proof systems. Computational Complexity, 3(3):292-305, 1993.

• Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 280-293, Amsterdam, The Netherlands, 28 June-1 July 1994. IEEE Computer Society Press.

• Anne Condon and Richard J. Lipton. On the complexity of space bounded interactive proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 462-467, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Stephen A. Cook. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 151-158, Shaker Heights, Ohio, 3-5 1971 1971.

• U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, pages 2-12, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 733-744, Victoria, British Columbia, Canada, 4-6 May 1992.

• Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. In Proceedings, Structure in Complexity Theory, Third Annual Conference, pages 156-161, Georgetown University, Washington D.C., 14-17 June 1988. IEEE Computer Society Press.

• Lance Fortnow and Michael Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28(5):249-251, 12 August 1988.

• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, February 1989.

• Johan Håstad. Clique is hard to approximate within n^{1 - epsilon}. In 37th Annual Symposium on Foundations of Computer Science, pages 627-636, Burlington, Vermont, 14-16 October 1996. IEEE.

• Johan Håstad. Some optimal inapproximability results. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 1-10, El Paso, Texas, 4-6 May 1997.

• M. Kiwi, C. Lund, A. Russell, D. Spielman, and R. Sundaram. Alternation in interaction. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 294-303, Amsterdam, The Netherlands, 28 June-1 July 1994. IEEE Computer Society Press.

• Dror Lapidot and Adi Shamir. Fully parallelized multi prover protocols for NEXP-time (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, pages 13-18, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Richard J. Lipton. Efficient checking of computations. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 207-215, Rouen, France, 22-24 February 1990. Springer.

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, October 1992.

• Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, September 1994.

• Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, August 1993.

• Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, December 1991.

• Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 194-203, Montréal, Québec, Canada, 23-25 May 1994.

• Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 475-484, El Paso, Texas, 4-6 May 1997.

• Ronitt Rubinfeld and Madhu Sudan. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 23-32, Orlando, Florida, 27-29 January 1992.

• Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, October 1992.

• David Zuckerman. Simulating BPP using a general weak random source. In 32nd Annual Symposium on Foundations of Computer Science, pages 79-89, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• David Zuckerman. NP-complete problems have a version that's hard to approximate. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 305-312, San Diego, California, 18-21 May 1993. IEEE Computer Society Press.

Shortcuts: