{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,6]],"date-time":"2026-11-06T04:11:18Z","timestamp":1793938278960,"version":"4.8.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T00:00:00Z","timestamp":1512950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1149888,CCF-1525342,CCF-1527110,CCF-1618280"],"award-info":[{"award-number":["CCF-1149888,CCF-1525342,CCF-1527110,CCF-1618280"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Packard Fellowship in Science and Engineering"},{"name":"European Community s Seventh Framework Programme","award":["257575"],"award-info":[{"award-number":["257575"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability \u03b5. We analyze the minimal overhead that must be added by the coding scheme to succeed in performing the computation despite the noise.<\/jats:p>\n          <jats:p>\n            Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with\n            <jats:italic>n<\/jats:italic>\n            parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating\n            <jats:italic>T<\/jats:italic>\n            bits over the noise-free network, but for which any protocol with success probability of 1-\n            <jats:italic>o<\/jats:italic>\n            (1) must communicate at least \u03a9 (\n            <jats:italic>T<\/jats:italic>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\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            <jats:italic>n<\/jats:italic>\n            factor.\n          <\/jats:p>\n          <jats:p>\n            We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is \u0398 (log log\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            ). Our bounds prove that, despite several previous coding schemes with rate \u03a9 (1) for certain topologies, no coding scheme with constant rate \u03a9 (1) exists for arbitrary\n            <jats:italic>n<\/jats:italic>\n            -party noisy networks.\n          <\/jats:p>","DOI":"10.1145\/3050218","type":"journal-article","created":{"date-parts":[[2017,12,13]],"date-time":"2017-12-13T14:50:37Z","timestamp":1513176637000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Constant-Rate Coding for Multiparty Interactive Communication Is Impossible"],"prefix":"10.1145","volume":"65","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3615-3239","authenticated-orcid":false,"given":"Klim","family":"Efremenko","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, ISRAEL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Gelles","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, ISRAEL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541368"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933085"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661628"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090250"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.33"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897563"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2734881"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2353994"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.73"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.55"},{"key":"e_1_2_1_11_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2582176"},{"key":"e_1_2_1_13_1","volume-title":"Open Problems in Communication and Computation, Thomas M","author":"Gamal Abbas El"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2367094"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.2626"},{"key":"e_1_2_1_16_1","volume-title":"Coding for Interactive Communication: A Survey. Foundations and Trends\u00ae in Theoretical Computer Science 13, 1--2","author":"Gelles Ran","year":"2015"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1052202"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884570"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS\u201917)","author":"Gelles Ran"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.51"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2294186"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2483323"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.49"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591872"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654864"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.32"},{"key":"e_1_2_1_27_1","volume-title":"Schulman","author":"Hoza William M.","year":"2016"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688109"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488699"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_1_31_1","volume-title":"Balancing communication for multi-party interactive coding","author":"Lewko Allison","year":"2015"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11235-011-9433-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222016"},{"key":"e_1_2_1_34_1","volume-title":"Translated under the title \u2018Information and Information Stability of Random Variables and Processes","author":"Pinsker M. S."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1731"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195462"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267778"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167279"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/584091.584093"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3050218","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3050218","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3050218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:26Z","timestamp":1750217786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3050218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,11]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3050218"],"URL":"https:\/\/doi.org\/10.1145\/3050218","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,11]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}