Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation -- automata, bounded-action devices; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- alternation and nondeterminism, probabilistic computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes -- relations among complexity classes
General Terms: Theory
Additional Key Words and Phrases: Arthur-Merlin games, interactive proof systems, probabilistic game automata
Selected papers that cite this one
- Anne Condon and Richard Ladner. Interactive proof systems with polynomially bounded strategies. Journal of Computer and System Sciences, 50(3):506-518, June 1995.
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, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 1-10, Chicago, Illinois, 2-4 May 1988.
- Gilles Brassard and Claude Crepeau. Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond. In 27th Annual Symposium on Foundations of Computer Science, pages 188-195, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.
- Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114-133, January 1981.
- David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 11-19, Chicago, Illinois, 2-4 May 1988.
- 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.
- Uriel Feige, Amos Fiat, and Adi Shamir. Zero knowledge proofs of identity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 210-217, New York City, 25-27 May 1987.
- 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 and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 365-377, San Francisco, California, 5-7 May 1982.
- 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.
- Joe Kilian. Zero-knowledge with log-space verifiers. In 29th Annual Symposium on Foundations of Computer Science, pages 25-35, White Plains, New York, 24-26 October 1988. IEEE.
- Gary L. Peterson and John H. Reif. Multiple-person alternation. In 20th Annual Symposium on Foundations of Computer Science, pages 348-363, San Juan, Puerto Rico, 29-31 October 1979. IEEE.
- Martin Tompa and Heather Woll. Random self-reducibility and zero knowledge interactive proofs of possession of information. In 28th Annual Symposium on Foundations of Computer Science, pages 472-482, Los Angeles, California, 12-14 October 1987. IEEE.