Round Complexity Versus Randomness Complexity in Interactive Proofs

by Maya Leshkowitz

Theory of Computing, Volume 18(13), pp. 1-65, 2022

Bibliography with links to cited articles

[1]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

[2]   László Babai and Shlomo Moran: Arthur–Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-0000(88)90028-1]

[3]   Mihir Bellare, Oded Goldreich, and Shafi Goldwasser: Randomness in interactive proofs. Comput. Complexity, 3(4):319–354, 1993. [doi:10.1007/BF01275487]

[4]   Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos: On completeness and soundness in interactive proof systems. In Silvio Micali, editor, Randomness and Computation, volume 5 of Adv. Comput. Res., pp. 429–442. JAI Press, 1989. Author’s website.

[5]   Oded Goldreich and Maya Leshkowitz: On emulating interactive proofs with public coins. In Oded Goldreich, editor, Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation, pp. 178–198. Springer, 2020. [doi:10.1007/978-3-030-43662-9_12, ECCC:TR16-066]

[6]   Oded Goldreich, Silvio Micali, and Avi Wigderson: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):690–728, 1991. Preliminary version in FOCS’86. [doi:10.1145/116825.116852]

[7]   Oded Goldreich, Salil P. Vadhan, and Avi Wigderson: On interactive proofs with a laconic prover. Comput. Complexity, 11(1–2):1–53, 2002. [doi:10.1007/s00037-002-0169-0]

[8]   Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85. [doi:10.1137/0218012]

[9]   Shafi Goldwasser and Michael Sipser: Private coins versus public coins in interactive proof systems. In Silvio Micali, editor, Randomness and Computation, volume 5 of Adv. Comput. Res., pp. 73–90. JAI Press, 1989. Preliminary version in STOC’86.

[10]   Adam R. Klivans and Dieter van Melkebeek: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501–1526, 2002. [doi:10.1137/S0097539700389652]

[11]   Maya Leshkowitz: Round complexity versus randomness complexity in interactive proofs. In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOM’18), pp. 49:1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.49]

[12]   Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146605]

[13]   Ronen Shaltiel and Christopher Umans: Low-end uniform hardness versus randomness tradeoffs for AM. SIAM J. Comput., 39(3):1006–1037, 2009. [doi:10.1137/070698348]

[14]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146609]