Multiparty Karchmer-Wigderson Games and Threshold Circuits

by Alexander Kozachinskiy and Vladimir Podolskii

Theory of Computing, Volume 18(15), pp. 1-33, 2022

Bibliography with links to cited articles

[1]   Miklós Ajtai, János Komlós, and Endre Szemerédi: Sorting in clog n parallel steps. Combinatorica, 3(1):1–19, 1983. Preliminary version in STOC’83. [doi:10.1007/BF02579338]

[2]   Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, and Ron D. Rothblum: Efficient multiparty protocols via log-depth threshold formulae. In Proc. 33rd Ann. Internat. Cryptology Conf. (CRYPTO’13), pp. 185–202. Springer, 2013. [doi:10.1007/978-3-642-40084-1_11, ECCC:TR13-107]

[3]   Irit Dinur and Or Meir: Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. Comput. Complexity, 27(3):375–462, 2018. Preliminary version in CCC’16. [doi:10.1007/s00037-017-0159-x]

[4]   Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson: Toward better formula lower bounds: The composition of a function and a universal relation. SIAM J. Comput., 46(1):114–131, 2017. Preliminary version in STOC’14. [doi:10.1137/15M1018319, ECCC:TR13-190]

[5]   Oded Goldreich: On (Valiant’s) polynomial-size monotone formula for majority. In Oded Goldreich, editor, Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation, pp. 17–23. Springer, 2020. Earlier versions on author’s website: 2011 version, 2019 version. [doi:10.1007/978-3-030-43662-9_3]

[6]   Mika Göös and Toniann Pitassi: Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778–1806, 2018. Preliminary version in STOC’14. [doi:10.1137/16M1082007]

[7]   Arvind Gupta and Sanjeev Mahajan: Using amplification to compute majority with small majority gates. Comput. Complexity, 6(1):46–63, 1996. [doi:10.1007/BF01202041]

[8]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Springer, 2012. Summary in Bull. EATCS 2014. [doi:10.1007/978-3-642-24508-4]

[9]   Mauricio Karchmer, Ran Raz, and Avi Wigderson: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complexity, 5(3–4):191–204, 1995. Preliminary version in SCT’91. [doi:10.1007/BF01206317]

[10]   Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discr. Math., 3(2):255–265, 1990. Preliminary version in STOC’88. [doi:10.1137/0403021]

[11]   Alexander Kozachinskiy and Vladimir Podolskii: Multiparty Karchmer–Wigderson games and threshold circuits. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 24:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.24]

[12]   Anup Rao and Amir Yehudayoff: Communication Complexity and Applications. Cambridge Univ. Press, 2020. [doi:10.1017/9781108671644]

[13]   Ran Raz and Pierre McKenzie: Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999. Preliminary version in FOCS’97. [doi:10.1007/s004930050062]

[14]   Dmitry Sokolov: Dag-like communication and its applications. In Proc. Comp. Sci. Symp. in Russia (CSR’17), pp. 294–307. Springer, 2017. [doi:10.1007/978-3-319-58747-9_26, ECCC:TR16-202]

[15]   Leslie G. Valiant: Short monotone formulae for the majority function. J. Algorithms, 5(3):363–366, 1984. [doi:10.1016/0196-6774(84)90016-6]