@article{6b2540fc51554a8fa01842be895ed349,
title = "Constant-rate coding for multiparty interactive communication is impossible",
abstract = "We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability ϵ. We analyze the minimal overhead that must be added by the coding scheme to succeed in performing the computation despite the noise. Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1 o(1) must communicate at least ω(T log nlog log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log logn factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is θ(log logn/ logn). Our bounds prove that, despite several previous coding schemes with rate ω(1) for certain topologies, no coding scheme with constant rate ω(1) exists for arbitrary n-party noisy networks.",
keywords = "Coding theory, Communication complexity, Lower bounds, Multiparty interactive communication, Random noise, Star network",
author = "Mark Braverman and Klim Efremenko and Ran Gelles and Bernhard Haeupler",
note = "Funding Information: This article is supported in part by an NSF CAREER award (CCF-1149888), NSF CCF-1525342 and DMS-1128155, a Packard Fellowship in Science and Engineering, the Simons Collaboration on Algorithms and Geometry, the European Community{\textquoteright}s Seventh Framework Programme (FP7/2007-2013) under Grant Agreement No. 257575, ISF Grant No. 1078/17, NSF Grants No. CCF-1527110 and No. CCF-1618280. Authors{\textquoteright} addresses: M. Braverman, Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ 08540, USA; email: mbraverm@cs.princeton.edu; K. Efremenko, Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva 84105, ISRAEL; email: klimefrem@gmail.com; R. Gelles (corresponding author), Faculty of Engineering, Bar-Ilan University, Ramat-Gan 52900, ISRAEL; email: ran.gelles@biu.ac.il; B. Haeupler, Computer Science Department, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15213, USA; email: haeupler@cs.cmu.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2017 ACM 0004-5411/2017/12-ART4 $15.00 https://doi.org/10.1145/3050218 Publisher Copyright: {\textcopyright} 2017 ACM.",
year = "2017",
month = dec,
doi = "10.1145/3050218",
language = "English (US)",
volume = "65",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "1",
}