Preliminary versionA preliminary version of these results was presented in: Adi Shamir. IP = PSPACE. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 11-15, St. Louis, Missouri, 22-24 October 1990. IEEE.
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.
- 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.
- Uriel Feige and Joe Kilian. Making games short (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 506-516, El Paso, Texas, 4-6 May 1997.
- 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.
- Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, and Alan L. Selman. P-selective sets and reducing search to decision vs self-reducibility. Journal of Computer and System Sciences, 53(2):194-209, October 1996.
- Lane A. Hemaspaandra and Riccardo Silvestri. Easily checked generalized self-reducibility. SIAM Journal on Computing, 24(4):840-858, August 1995.
- L. A. Hemaspaandra and M. Zimand. Strong self-reducibility precludes strong immunity. Mathematical Systems Theory, 29(5):535-548, September/October 1996.
- 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.
- Steven M. Kautz and Peter Bro Miltersen. Relative to a random oracle, NP is not small. Journal of Computer and System Sciences, 53(2):235-250, October 1996.
- Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Fast algorithms for finding randomized strategies in game trees. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 750-759, Montréal, Québec, Canada, 23-25 May 1994.
- Patrick D. Lincoln, John C. Mitchell, and Andre Scedrov. Linear logic proof games and optimization. The Bulletin of Symbolic Logic, 2(3):322-338, September 1996.
- 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.
- Christos H. Papadimitriou and Mihalis Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. Journal of Computer and System Sciences, 53(2):161-170, October 1996.
- 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.
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.
- 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.
- Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 291-304, Providence, Rhode Island, 6-8 May 1985.
- Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 59-68, Berkeley, California, 28-30 May 1986.
- Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 2-10, St. Louis, Missouri, 22-24 October 1990. IEEE.
- 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.