The Layer Complexity of Arthur-Merlin-like Communication

by Dmitry Gavinsky

Theory of Computing, Volume 17(8), pp. 1-28, 2021

Bibliography with links to cited articles

[1]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):1–54, 2009. Preliminary version in STOC’08. [doi:10.1145/1490270.1490272]

[2]   Harold Abelson: Lower bounds on information transfer in distributed computations. J. ACM, 27(2):384–392, 1980. Preliminary version in FOCS’78. [doi:10.1145/322186.322200]

[3]   László Babai, Péter Frankl, and Janos Simon: Complexity classes in communication complexity theory. In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc., 1986. [doi:10.1109/SFCS.1986.15]

[4]   Elmar Böhler, Christian Glaßer, and Daniel Meister: Error-bounded probabilistic computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001]

[5]   Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Vasudevan: On the power of statistical zero knowledge. SIAM J. Comput., 49(4):1–58, 2020. Preliminary version in FOCS’17. [doi:10.1137/17M1161749, arXiv:1609.02888]

[6]   Lijie Chen: On the hardness of approximate and exact (bichromatic) maximum inner product. Theory of Computing, 16(4):1–50, 2020. Preliminary version in CCC’18. [doi:10.4086/toc.2020.v016a004]

[7]   Evgeny Drukh and Yishay Mansour: Concentration bounds for unigram language models. JMLR, 6(42):1231–1264, 2005. JMLR.

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

[9]   Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman: Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835–1869, 2016. Preliminary version in STOC’15. [doi:10.1137/15M103145X]

[10]   Mika Göös, Toniann Pitassi, and Thomas Watson: Zero-information protocols and unambiguity in Arthur–Merlin communication. Algorithmica, 76(3):684–719, 2016. Preliminary version in ITCS’15. [doi:10.1007/s00453-015-0104-9]

[11]   Mika Göös, Toniann Pitassi, and Thomas Watson: The landscape of communication complexity classes. Comput. Complexity, 27(2):245–304, 2018. [doi:10.1007/s00037-018-0166-6]

[12]   Mauricio Karchmer, Ilan Newman, Mike Saks, and Avi Wigderson: Non-deterministic communication complexity with few witnesses. J. Comput. System Sci., 49(2):247–257, 1994. Preliminary version in SCT(CCC)’92. [doi:10.1016/S0022-0000(05)80049-2]

[13]   Hartmut Klauck: Rectangle size bounds and threshold covers in communication complexity. In Proc. 18th IEEE Conf. on Comput. Complexity (CCC’03), pp. 118–134. IEEE Comp. Soc., 2003. [doi:10.1109/CCC.2003.1214415, arXiv:cs/0208006]

[14]   Hartmut Klauck: On Arthur Merlin games in communication complexity. In Proc. 26th IEEE Conf. on Comput. Complexity (CCC’11), pp. 189–199. IEEE Comp. Soc., 2011. [doi:10.1109/CCC.2011.33, arXiv:1101.0523]

[15]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511574948]

[16]   John von Neumann: Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1):295–320, 1928. EuDML.

[17]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]