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.