Separation of Unbounded-Error Models in Multi-Party Communication Complexity

by Arkadev Chattopadhyay and Nikhil S. Mande

Theory of Computing, Volume 14(21), pp. 1-23, 2018

Bibliography with links to cited articles

[1]   Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, and Phuong Nguyen: The NOF multiparty communication complexity of composed functions. Comput. Complexity, 24(3):645–694, 2015. Preliminary version in ICALP’12. [doi:10.1007/s00037-013-0078-4]

[2]   László Babai, Peter 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]

[3]   László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam: Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137–166, 2003. Preliminary version in STACS’95. [doi:10.1137/S0097539700375944]

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

[5]   Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel: Separating deterministic from randomized multiparty communication complexity. Theory of Computing, 6(9):201–225, 2010. Preliminary version in ICALP’07. [doi:10.4086/toc.2010.v006a009]

[6]   Paul Beame and Dang-Trinh Huynh-Ngoc: Multiparty communication complexity and threshold circuit size of AC0. SIAM J. Comput., 41(3):484–518, 2012. Preliminary version in FOCS’09. [doi:10.1137/100792779]

[7]   Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. Comput. Complexity, 4(4):339–349, 1994. Preliminary version in SCT’92. [doi:10.1007/BF01263422]

[8]   Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.18]

[9]   Mark Bun and Justin Thaler: Approximate degree and the complexity of depth three circuits. In Proc. 22nd Internat. Workshop on Randomization and Computation (RANDOM’18), pp. 35:1–35:18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.35]

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

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

[12]   Arkadev Chattopadhyay: Circuits, Communication and Polynomials. Ph. D. thesis, McGill University, 2009.

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

[14]   Arkadev Chattopadhyay and Nikhil Mande: Small error versus unbounded error protocols in the NOF model. Electron. Colloq. on Comput. Complexity (ECCC), September 2016. [ECCC:TR16-095]

[15]   Arkadev Chattopadhyay and Michael E. Saks: The power of super-logarithmic number of players. In Proc. 18th Internat. Workshop on Randomization and Computation (RANDOM’14), pp. 596–603. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.596]

[16]   Andrew Drucker, Fabian Kuhn, and Rotem Oshman: On the power of the congested clique model. In Proc. 33th Symp. on Principles of Distributed Comput. (PODC’14), pp. 367–376. ACM Press, 2014. [doi:10.1145/2611462.2611493]

[17]   Mikael Goldmann, Johan Håstad, and Alexander A. Razborov: Majority gates vs. general weighted threshold gates. Comput. Complexity, 2(4):277–300, 1992. Preliminary version in SCT’92. [doi:10.1007/BF01200426]

[18]   Vince Grolmusz: The BNS lower bound for multi-party protocols in nearly optimal. Inform. and Comput., 112(1):51–54, 1994. [doi:10.1006/inco.1994.1051]

[19]   Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii: Polynomial threshold functions and boolean threshold circuits. Inform. and Comput., 240:56–73, 2015. Preliminary version in MFCS’13. [doi:10.1016/j.ic.2014.09.008]

[20]   Johan Håstad: On the size of weights for threshold gates. SIAM J. Discrete Math., 7(3):484–492, 1994. [doi:10.1137/S0895480192235878]

[21]   Hamed Hatami, Kaave Hosseini, and Shachar Lovett: Structure of protocols for XOR functions. In Proc. 57th FOCS, pp. 282–288. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.38]

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

[23]   Eyal Kushilevitz and Noam Nisan: Communication complexity. Cambridge University Press, 1997.

[24]   Troy Lee and Adi Shraibman: Disjointness is hard in the multiparty number-on-the-forehead model. Comput. Complexity, 18(2):309–336, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0276-2]

[25]   Mihai Pǎtraşcu: Towards polynomial lower bounds for dynamic problems. In Proc. 42nd STOC, pp. 603–610. ACM Press, 2010. [doi:10.1145/1806689.1806772]

[26]   Anup Rao and Amir Yehudayoff: Simplified lower bounds on the multiparty communication complexity of disjointness. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), pp. 88–101. DROPS, 2015. [doi:10.4230/LIPIcs.CCC.2015.88]

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

[28]   Alexander A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. Preliminary version in ICALP’90. [doi:10.1016/0304-3975(92)90260-M]

[29]   Alexander A. Sherstov: Halfspace matrices. Comput. Complexity, 17(2):149–178, 2008. Preliminary version in CCC’07. [doi:10.1007/s00037-008-0242-4]

[30]   Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. SIAM J. Comput., 42(6):2329–2374, 2013. Preliminary version in FOCS’09. [doi:10.1137/100785260]

[31]   Alexander A. Sherstov: Communication lower bounds using directional derivatives. J. ACM, 61(6):34:1–34:71, 2014. Preliminary version in STOC’13. [doi:10.1145/2629334]

[32]   Alexander A. Sherstov: Private Communication, 2016.

[33]   Alexander A. Sherstov: The multiparty communication complexity of set disjointness. SIAM J. Comput., 45(4):1450–1489, 2016. Preliminary version in STOC’12. [doi:10.1137/120891587]

[34]   Alexander A. Sherstov: On multiparty communication with large versus unbounded error. Theory of Computing, 14(22), 2018. Preliminary version ECCC TR16-138. [doi:10.4086/toc.2018.v014a022]

[35]   Justin Thaler: Lower bounds for the approximate degree of block-composed functions. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 17:1–17:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.17, ECCC:TR14-150]

[36]   Shengyu Zhang: Efficient quantum protocols for XOR functions. In Proc. 25th SODA, pp. 1878–1885. ACM Press, 2014. [doi:10.1137/1.9781611973402.136]