Journal of the ACM Bibliography

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

Additional Key Words and Phrases: NP-completeness, optimization, proof verification, randomness

Selected references

• Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In 37th Annual Symposium on Foundations of Computer Science, pages 2-11, Burlington, Vermont, 14-16 October 1996. IEEE.

• Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317-331, April 1997.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, January 1998.

• 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.

• G. Ausiello, A. D'Atri, and M. Protasi. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21(1):136-153, August 1980.

• G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi. Toward a unified approach for the classification of NP-complete optimization problems. Theoretical Computer Science, 12(1):83-96, September 1980.

• 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. Transparent (holographic) proofs. In 10th Annual Symposium on Theoretical Aspects of Computer Science, volume 665 of Lecture Notes in Computer Science, pages 525-534, Würzburg, Germany, 25-27 February 1993. Springer.

• László Babai and Lance Fortnow. Arithmetization: A new method in structural complexity theory. Computational Complexity, 1:41-66, 1991.

• 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.

• László Babai and Shlomo Moran. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36(2):254-276, April 1988.

• Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37-48, Rouen, France, 22-24 February 1990. Springer.

• 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 nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.

• 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.

• Piotr Berman and Georg Schnitger. On the complexity of approximating the independent set problem. Information and Computation, 96(1):77-94, January 1992.

• Marshall Bern and Paul Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171-176, 1 September 1989.

• Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630-647, July 1994.

• 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. Journal of Computer and System Sciences, 47(3):549-595, December 1993.

• Jin-yi Cai, Anne Condon, and Richard J. Lipton. PSPACE is provable by two provers in one round. Journal of Computer and System Sciences, 48(1):183-193, February 1994.

• Aviad Cohen and Avi Wigderson. Dispersers, deterministic amplification, and weak random sources (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 14-19, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter Shor. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 305-314, San Diego, California, 16-18 May 1993.

• 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.

• E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864-894, August 1994.

• Uriel Feige. A threshold of ln n for approximating set cover (preliminary version). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 314-318, Philadelphia, Pennsylvania, 22-24 May 1996.

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996.

• Uriel Feige and Joe Kilian. Two prover protocols -- low error at affordable rates (preliminary version). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 172-183, Montréal, Québec, Canada, 23-25 May 1994.

• Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number (preliminary version). In Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pages 278-287, Philadelphia, Pennsylvania, 24-27 May 1996. IEEE Computer Society Press.

• 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. Theoretical Computer Science, 134(2):545-557, 21 November 1994. Note.

• R\=usi\c{n}\v{s} Freivalds. Fast probabilistic algorithms. In J. Be\v{c}vá\v{r}, editor, Mathematical Foundations of Computer Science 1979, volume 74 of Lecture Notes in Computer Science, pages 57-69, Olomouc, Czechoslovakia, 3-7 September 1979. Springer-Verlag.

• Katalin Friedl, Zsolt Hátsági, and Alexander Shen. Low-degree tests. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 57-64, Arlington, Virginia, 23-25 January 1994.

• Martin Fürer. Improved hardness results for approximating the chromatic number. In 36th Annual Symposium on Foundations of Computer Science, pages 414-421, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• M. R. Garey and D. S. Johnson. Scheduling tasks with nonuniform deadlines on two processors. Journal of the ACM, 23(3):461-467, July 1976.

• M. R. Garey and D. S. Johnson. ``Strong'' NP-completeness results: Motivation, examples, and implications. Journal of the ACM, 25(3):499-508, July 1978.

• M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, February 1976.

• Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 32-42, New Orleans, Louisiana, 6-8 May 1991.

• Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43(4):169-174, 28 September 1992.

• Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, November 1995.

• 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. Testing of the long code and hardness for clique. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 11-19, Philadelphia, Pennsylvania, 22-24 May 1996.

• 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.

• Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463-468, October 1975.

• Russell Impagliazzo and David Zuckerman. How to recycle random bits. In 30th Annual Symposium on Foundations of Computer Science, pages 248-253, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256-278, December 1974.

• Viggo Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37(1):27-35, 10 January 1991.

• David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18(1):82-98, May 1997.

• Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. In 35th Annual Symposium on Foundations of Computer Science, pages 819-830, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Phokion G. Kolaitis and Moshe Y. Vardi. The decision problem for the probabilities of higher-order properties. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 425-435, New York City, 25-27 May 1987.

• Dror Lapidot and Adi Shamir. Fully parallelized multi-prover protocols for NEXP-time. Journal of Computer and System Sciences, 54(2):215-220, April 1997.

• 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. The approximation of maximum subgraph problems. In Svante Carlsson Andrzej Lingas, Rolf G. Karlsson, editor, Automata, Languages and Programming, 20th International Colloquium, volume 700 of Lecture Notes in Computer Science, pages 40-51, Lund, Sweden, 5-9 July 1993. Springer-Verlag.

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

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

• A. Paz and S. Moran. Non deterministic polynomial optimization problems and their approximations. Theoretical Computer Science, 15(3):251-277, September 1981.

• 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. A parallel repetition theorem. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 447-456, Las Vegas, Nevada, 29 May-1 June 1995.

• 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. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, April 1996.

• Sartaj Sahni. Approximate algorithms for the 0/1 knapsack problem. Journal of the ACM, 22(1):115-124, January 1975.

• Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555-565, July 1976.

• J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, October 1980.

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

• Gábor Tardos. Multi-prover encoding schemes and three-prover proof systems. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 308-317, Amsterdam, The Netherlands, 28 June-1 July 1994. IEEE Computer Society Press.

• Mihalis Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 17(3):475-502, November 1994.

• David Zuckerman. On unapproximable versions of NP-complete problems. SIAM Journal on Computing, 25(6):1293-1304, December 1996.

Shortcuts: