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]