Skip to main content

Constant-rate coding for multiparty interactive communication is impossible

Author(s): Braverman, Mark; Efremenko, K; Gelles, Ran; Haeupler, B

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1v37c
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorEfremenko, K-
dc.contributor.authorGelles, Ran-
dc.contributor.authorHaeupler, B-
dc.date.accessioned2018-07-20T15:06:54Z-
dc.date.available2018-07-20T15:06:54Z-
dc.date.issued2016-06-19en_US
dc.identifier.citationBraverman, M, Efremenko, K, Gelles, R, Haeupler, B. (2016). Constant-rate coding for multiparty interactive communication is impossible. 19-21-June-2016 (999 - 1010. doi:10.1145/2897518.2897563en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1v37c-
dc.description.abstractWe 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 in order 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 n / log 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 log n 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 log n / log n). 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.en_US
dc.format.extent999 - 1010en_US
dc.relation.ispartofSTOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleConstant-rate coding for multiparty interactive communication is impossibleen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1145/2897518.2897563-
dc.date.eissued2016-06-19en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Constant-rate coding for multiparty interactive communication is impossible.pdf539.58 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.