On Multiparty Communication with Large versus Unbounded Error

by Alexander A. Sherstov

Theory of Computing, Volume 14(22), pp. 1-17, 2018

Bibliography with links to cited articles

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

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

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

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

[5]   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. Preliminary version in ICALP’05. [doi:10.1137/060654645]

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

[7]   Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf: Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379–395, 2007. Preliminary version in STACS’05. [doi:10.1007/s00224-006-1313-z, arXiv:quant-ph/0309220]

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

[10]   Arkadev Chattopadhyay: Circuits, Communication, and Polynomials. Ph. D. thesis, McGill University, 2008. eScholarship@McGill.

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

[12]   Arkadev Chattopadhyay and Nikhil Mande: Separation of unbounded-error models in multi-party communication complexity. Theory of Computing, 14(21), 2018. Preliminary version ECCC TR16-095. [doi:10.4086/toc.2018.v014a021]

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

[14]   Matei David, Toniann Pitassi, and Emanuele Viola: Improved separations between nondeterministic and randomized multiparty communication. ACM Trans. Comput. Theory, 1(2/5), 2009. Preliminary version in RANDOM’08. [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(10):227–245, 2010. [doi:10.4086/toc.2010.v006a010, arXiv:1004.0817]

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

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

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

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

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

[21]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106–123, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-0000(86)90046-2]

[22]   Alexander A. Razborov: Quantum communication complexity of symmetric predicates. Izv. Math., 67(1):145–159, 2003. [doi:10.1070/IM2003v067n01ABEH000422, arXiv:quant-ph/0204025]

[23]   Alexander A. 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. Version available at CiteSeer. [doi:10.1016/0020-0190(93)90041-7]

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

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

[26]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. Preliminary version in STOC’08. [doi:10.1137/080733644]

[27]   Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica, 33(1):73–96, 2013. Preliminary version in STOC’10. [doi:10.1007/s00493-013-2759-7]

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

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

[30]   Alexander A. Sherstov: On multiparty communication with large versus unbounded error. Electron. Colloq. on Comput. Complexity (ECCC), 23:138, 2016. [ECCC:TR16-138]

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

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