A Separation of NP and coNP in Multiparty Communication Complexity

by Dmitry Gavinsky and Alexander A. Sherstov

Theory of Computing, Volume 6(10), pp. 227-245, 2010

Bibliography with links to cited articles

[1]   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. Press, 1986. [doi:10.1109/SFCS.1986.15]

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

[3]   Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel: Separating deterministic from randomized multiparty communication complexity. Theory of Computing, 6:201–225, 2010. [doi:10.4086/toc.2010.v006a009]

[4]   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]

[5]   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]

[6]   Arkadev Chattopadhyay: Discrepancy and the power of bottom fan-in in depth-three circuits. In Proc. 48th FOCS, pp. 449–458. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.30]

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

[8]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. [doi:10.1137/0217015]

[9]   Fan R. K. Chung and Prasad Tetali: Communication complexity and quasi randomness. SIAM J. Discrete Math., 6(1):110–123, 1993. [doi:10.1137/0406009]

[10]   Matei David and Toniann Pitassi: Separating NOF communication complexity classes RP and NP. In Electron. Colloq. on Comput. Complexity (ECCC), February 2008. Report TR08-014. [ECCC:TR08-014]

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

[12]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/toc.gs.2008.001]

[13]   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]

[14]   Bala Kalyanasundaram and Georg Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992. [doi:10.1137/0405044]

[15]   Hartmut Klauck: Lower bounds for quantum communication complexity. In Proc. 42nd FOCS, pp. 288–297. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959903]

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

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

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

[19]   Noam Nisan and Mario Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, 1994. [doi:10.1007/BF01263419]

[20]   Christos H. Papadimitriou and Michael Sipser: Communication complexity. In Proc. 14th STOC, pp. 196–200. ACM Press, 1982. [doi:10.1145/800070.802192]

[21]   Ramamohan Paturi: On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pp. 468–474. ACM Press, 1992. [doi:10.1145/129712.129758]

[22]   Ran Raz: The BNS-Chung criterion for multi-party communication complexity. Comput. Complexity, 9(2):113–122, 2000. [doi:10.1007/PL00001602]

[23]    A. A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. [doi:10.1016/0304-3975(92)90260-M]

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

[25]   Alexander Razborov and Avi Wigderson: nΩ(log n) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inform. Process. Lett., 45(6):303–307, 1993. [doi:10.1016/0020-0190(93)90041-7]

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

[27]   Alexander A. Sherstov: The pattern matrix method for lower bounds on quantum communication. In Proc. 40th STOC, pp. 85–94. ACM Press, 2008. [doi:10.1145/1374376.1374392]

[28]   Alexander A. Sherstov: Separating AC0 from depth-2 majority circuits. SIAM J. Comput., 38(6):2113–2129, 2009. Preliminary version in 39th STOC, 2007. [doi:10.1137/08071421X]

[29]   Yaoyun Shi and Yufan Zhu: Quantum communication complexity of block-composed functions. Quantum Inf. Comput., 9(5–6):444–460, 2009.

[30]   Andrew Chi-Chih Yao: On ACC and threshold circuits. In Proc. 31st FOCS, pp. 619–627. IEEE Comp. Soc. Press, 1990. [doi:10.1109/FSCS.1990.89583]