Separating Deterministic from Randomized Multiparty Communication Complexity

by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel

Theory of Computing, Volume 6(9), pp. 201-225, 2010

Bibliography with links to cited articles

[1]   László Babai, Péter Frankl, and János Simon: Complexity classes in communication complexity theory (preliminary version). In Proc. 27th FOCS, pp. 337–347. IEEE Comput. Soc. Press, 1986. [doi:10.1109/SFCS.1986.15]

[2]   László Babai, Anna Gál, Peter Kimmel, and Satyanarayana Lokam: Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137–166, 2004. [doi:10.1137/S0097539700375944]

[3]   László Babai, Thomas Hayes, and Peter Kimmel: The cost of the missing bit: Communication complexity with help. Combinatorica, 21(4):455–488, 2001.

[4]   László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992. [doi:10.1016/0022-0000(92)90047-M]

[5]   Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel: Separating deterministic from nondeterministic NOF multiparty communication complexity. In Proc. 34th Intern. Colloq. Autom. Lang. Program. (ICALP), volume 4596 of LNCS, pp. 134–145. Springer, 2007.

[6]   Paul Beame, Trinh Huynh, and Toniann Pitassi: Hardness amplification in proof complexity. In Proc. 42nd STOC, pp. 87–96. ACM Press, 2010. [doi:10.1145/1806689.1806703]

[7]   Paul Beame and Dang-Trinh Huynh-Ngoc: Multiparty communication complexity and threshold circuit size of AC0. In Proc. 50th FOCS, pp. 53–62. IEEE Comput. Soc. Press, 2009. [doi:10.1109/FSCS.2009.12]

[8]   Paul Beame, Toniann Pitassi, and Nathan Segerlind: Lower bounds for Lovász–Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845–869, 2007. [doi:10.1137/060654645]

[9]   Richard Beigel, William Gasarch, and James Glenn: The multiparty communication complexity of Exact-T: Improved bounds and new problems. In Proc. 31st. Intern. Symp. Math. Found. Comput. Sci. (MFCS), volume 4162 of LNCS, pp. 146–156. Springer, 2006. [doi:10.1007/11821069_13]

[10]   Richard Beigel and Jun Tarui: On ACC. Comput. Complexity, 4(4):350–366, 1994. [doi:10.1007/BF01263423]

[11]   J. Lawrence Carter and Mark N. Wegman: Universal classes of hash functions. J. Comput. System Sci., 18(2):143–154, 1979. [doi:10.1016/0022-0000(79)90044-8]

[12]   Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton: Multi-party protocols. In Proc. 15th STOC, pp. 94–99. ACM Press, 1983. [doi:10.1145/800061.808737]

[13]   Arkadev Chattopadhyay and Anil Ada: Multiparty communication complexity of disjointness. Technical Report TR08-002, Electron. Colloq. on Comput. Complexity (ECCC), 2008.

[14]   Matei David, Toniann Pitassi, and Emanuele Viola: Improved separations between nondeterministic and randomized multiparty communication. ACM Trans. Comput. Log., 1(2):1–20, 2009. [doi:10.1145/1595391.1595392]

[15]   Dmitry Gavinsky and Alexander A. Sherstov: A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6:227–245, 2010. [doi:10.4086/toc2010.v006a010]

[16]   Johan Håstad and Mikael Goldmann: On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113–129, 1991. [doi:10.1007/BF01272517]

[17]   Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20–46, 2007. [doi:10.1137/S0097539702405620]

[18]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge University Press, 1997.

[19]   Troy Lee and Adi Shraibman: Disjointness is hard in the multi-party number-on-the-forehead model. In Proc. 23rd Comput. Complex. Conf. (CCC), pp. 81–91. IEEE Comput. Soc. Press, 2008. [doi:10.1109/CCC.2008.29]

[20]   Yishay Mansour, Noam Nisan, and Prasoon Tiwari: The computational complexity of universal hashing. Theoret. Comput. Sci., 107(1):121–133, 1993. [doi:10.1016/0304-3975(93)90257-T]

[21]   Ilan Newman: Private vs. common random bits in communication complexity. Inform. Process. Lett., 39(2):67–71, 1991. [doi:10.1016/0020-0190(91)90157-D]

[22]   Noam Nisan: The communication complexity of threshold gates. In Combinatorics, Paul Erdʺo    s is Eighty, number 1 in Bolyai Society Mathematical Studies, pp. 301–315. J. Bolyai Math. Soc., Budapest, 1993.

[23]   Noam Nisan and Avi Wigderson: Rounds in communication complexity revisited. SIAM J. Comput., 22(1):211–219, 1993. [doi:10.1137/0222016]

[24]   A. A. Razborov: Quantum communication complexity of symmetric predicates. Izv. Math., 67(1):145–159, 2003. [doi:10.1070/IM2003v067n01ABEH000422]

[25]   Alexander A. Sherstov: Communication lower bounds using dual polynomials. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 95:59–93, 2008.

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

[27]   Andrew Chi-Chih Yao: On ACC and threshold circuits. In Proc. 31st FOCS, volume 2, pp. 619–627, 1990. [doi:10.1109/FSCS.1990.89583]