Journal of the ACM Bibliography

Selected papers that cite this one

• M. Agrawal and V. Arvind. Geometric sets of low information content. Theoretical Computer Science, 158(1-2):193-219, 20 May 1996.

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

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

• D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. Journal of Cryptology, 10(1):17-36, Winter 1997.

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

• Manuel Blum and Sampath Kannan. Designing programs that check their work. Journal of the ACM, 42(1):269-291, January 1995.

• Anne Condon, Joan Feinberg, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997.

• Anne Condon and Richard Ladner. Interactive proof systems with polynomially bounded strategies. Journal of Computer and System Sciences, 50(3):506-518, June 1995.

• Stephen Cook, Russell Impagliazzo, and Tomoyuki Yamakami. A tight relationship between generic oracles and type-2 complexity theory. Information and Computation, 137(2):159-170, 15 September 1997.

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

• Lance Fortnow and Michael Sipser. Retraction of ``Probabilistic computation and linear time''. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, page 750, El Paso, Texas, 4-6 May 1997.

• Shafi Goldwasser. New directions in cryptography: Twenty some years later (or Cryptography and complexity theory: A match made in heaven). In 38th Annual Symposium on Foundations of Computer Science, pages 314-324, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Toshiya Itoh, Masafumi Hoshi, and Shigeo Tsujii. A low communication competitive interactive proof system for promised quadratic residuosity. Journal of Cryptology, 9(2):101-109, Spring 1996.

• Stuart A. Kurtz, Stephen R. Mahaney, and James S. Royer. The isomorphism conjecture fails relative to a random oracle. Journal of the ACM, 42(2):401-420, March 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.

• Alexander Russell and Ravi Sundaram. The relativized relationship between probabilistically checkable debate systems, IP and PSPACE. Information Processing Letters, 53(2):61-68, 27 January 1995.

• A. Shen. IP = PSPACE: Simplified proof. Journal of the ACM, 39(4):878-880, October 1992.

• Hal Wasserman and Manuel Blum. Software reliability via run-time result-checking. Journal of the ACM, 44(6):826-849, November 1997.

Selected references

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

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

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

• Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 174-187, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

• Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 302-309, Los Angeles, California, 28-30 April 1980.

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

• A. Shen. IP = PSPACE: Simplified proof. Journal of the ACM, 39(4):878-880, October 1992.

• Seinosuke Toda. On the computational power of PP and oplus P. In 30th Annual Symposium on Foundations of Computer Science, pages 514-519, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

Shortcuts: