The Layer Complexity of Arthur-Merlin-like Communication
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]