{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:49:06Z","timestamp":1787503746751,"version":"build-2736575974"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T00:00:00Z","timestamp":1495843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T00:00:00Z","timestamp":1495843200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-1149888"],"award-info":[{"award-number":["CCF-1149888"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Seventh Framework Programme","award":["257575"],"award-info":[{"award-number":["257575"]}]},{"name":"National Science Foundation","award":["CCF-1527110"],"award-info":[{"award-number":["CCF-1527110"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF-BSF"],"award-info":[{"award-number":["NSF-BSF"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s00446-017-0303-5","type":"journal-article","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T11:52:00Z","timestamp":1495885920000},"page":"505-515","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Reliable communication over highly connected noisy networks"],"prefix":"10.1007","volume":"32","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Braverman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klim","family":"Efremenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3615-3239","authenticated-orcid":false,"given":"Ran","family":"Gelles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,27]]},"reference":[{"key":"303_CR1","doi-asserted-by":"publisher","unstructured":"Agrawal, S., Gelles, R., Sahai, A.: Adaptive protocols for interactive communication. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 595\u2013599 (2016). doi:\n10.1109\/ISIT.2016.7541368","DOI":"10.1109\/ISIT.2016.7541368"},{"issue":"3","key":"303_CR2","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02783300","volume":"62","author":"N Alon","year":"1988","unstructured":"Alon, N.: The linear arboricity of graphs. Israel J. Math. 62(3), 311\u2013325 (1988)","journal-title":"Israel J. Math."},{"key":"303_CR3","doi-asserted-by":"publisher","unstructured":"Alon, N.: A parallel algorithmic version of the local lemma. In: 32nd Annual Symposium on Foundations of Computer Science (San Juan, PR, 1991), pp. 586\u2013593. IEEE Computer Society Press, Los Alamitos (1991). doi:\n10.1109\/SFCS.1991.185423","DOI":"10.1109\/SFCS.1991.185423"},{"key":"303_CR4","doi-asserted-by":"publisher","unstructured":"Alon, N., Braverman, M., Efremenko, K., Gelles, R., Haeupler, B.: Reliable communication over highly connected noisy networks. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC \u201916, pp. 165\u2013173 (2016). doi:\n10.1145\/2933057.2933085","DOI":"10.1145\/2933057.2933085"},{"key":"303_CR5","doi-asserted-by":"crossref","unstructured":"Alon, N., Capalbo, M.: Finding disjoint paths in expanders deterministically and online. In: 48th Annual Symposium on Foundations of Computer Science, (2007), pp. 518\u2013524. IEEE Computer Society Press, Los Alamitos (2007)","DOI":"10.1109\/FOCS.2007.19"},{"key":"303_CR6","volume-title":"The Probabilistic Method, 3rd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (2008). With an appendix on the life and work of Paul Erd\u0151s"},{"key":"303_CR7","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Kalai, Y.T.: Efficient interactive coding against adversarial noise. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 160\u2013166 (2012)","DOI":"10.1109\/FOCS.2012.22"},{"issue":"6","key":"303_CR8","doi-asserted-by":"publisher","first-page":"35:1","DOI":"10.1145\/2661628","volume":"61","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Kalai, Y.T., Naor, M.: Fast interactive coding against adversarial noise. J. ACM 61(6), 35:1\u201335:30 (2014). doi:\n10.1145\/2661628","journal-title":"J. ACM"},{"key":"303_CR9","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Naor, M.: Fast algorithms for interactive coding. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913, pp. 443\u2013456 (2013)","DOI":"10.1137\/1.9781611973105.32"},{"key":"303_CR10","doi-asserted-by":"crossref","unstructured":"Braverman, M., Efremenko, K.: List and unique coding for interactive communication in the presence of adversarial noise. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS \u201914, pp. 236\u2013245 (2014)","DOI":"10.1109\/FOCS.2014.33"},{"key":"303_CR11","doi-asserted-by":"crossref","unstructured":"Braverman, M., Efremenko, K., Gelles, R., Haeupler, B.: Constant-rate coding for multiparty interactive communication is impossible. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 999\u20131010 (2016)","DOI":"10.1145\/2897518.2897563"},{"key":"303_CR12","doi-asserted-by":"publisher","unstructured":"Braverman, M., Rao, A.: Towards coding for maximum errors in interactive communication. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 159\u2013166. ACM, New York (2011). doi:\n10.1145\/1993636.1993659","DOI":"10.1145\/1993636.1993659"},{"issue":"11","key":"303_CR13","doi-asserted-by":"publisher","first-page":"7248","DOI":"10.1109\/TIT.2014.2353994","volume":"60","author":"M Braverman","year":"2014","unstructured":"Braverman, M., Rao, A.: Toward coding for maximum errors in interactive communication. IEEE Trans. Inf. Theory 60(11), 7248\u20137255 (2014). doi:\n10.1109\/TIT.2014.2353994","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"303_CR14","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1137\/S0097539792232021","volume":"23","author":"A Broder","year":"1994","unstructured":"Broder, A., Frieze, A., Upfal, E.: Existence and construction of edge-disjoint paths on expander graphs. SIAM J. Comput. 23(5), 976\u2013989 (1994). doi:\n10.1137\/S0097539792232021","journal-title":"SIAM J. Comput."},{"issue":"2","key":"303_CR15","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1137\/S0097539795290805","volume":"28","author":"AZ Broder","year":"1998","unstructured":"Broder, A.Z., Frieze, A.M., Suen, S., Upfal, E.: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput. 28(2), 541\u2013573 (1998). doi:\n10.1137\/S0097539795290805","journal-title":"SIAM J. Comput."},{"issue":"6","key":"303_CR16","doi-asserted-by":"publisher","first-page":"2132","DOI":"10.1137\/100799642","volume":"42","author":"K Chandrasekaran","year":"2013","unstructured":"Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the Lov\u00e1sz local lemma. SIAM J. Comput. 42(6), 2132\u20132155 (2013)","journal-title":"SIAM J. Comput."},{"key":"303_CR17","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Pass, R., Telang, S.: Knowledge-preserving interactive coding. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 449\u2013458 (2013)","DOI":"10.1109\/FOCS.2013.55"},{"key":"303_CR18","unstructured":"Cook, N.A., Goldstein, L., Johnson, T.: Size biased couplings and the spectral gap for random regular graphs. arXiv preprint \narXiv:1510.06013\n\n (2015)"},{"key":"303_CR19","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, New York (2006)","edition":"2"},{"key":"303_CR20","doi-asserted-by":"publisher","unstructured":"Dolev, D., Lenzen, C., Peled, S.: Tri, Tri again: Finding triangles and small subgraphs in a distributed setting. In: Aguilera, M., (ed.) Distributed Computing, Lecture Notes in Computer Science, vol. 7611, pp. 195\u2013209. Springer, Berlin Heidelberg (2012). doi:\n10.1007\/978-3-642-33651-5_14","DOI":"10.1007\/978-3-642-33651-5_14"},{"issue":"8","key":"303_CR21","doi-asserted-by":"publisher","first-page":"4575","DOI":"10.1109\/TIT.2016.2582176","volume":"62","author":"K Efremenko","year":"2016","unstructured":"Efremenko, K., Gelles, R., Haeupler, B.: Maximal noise in interactive communication over erasure channels and channels with feedback. IEEE Trans. Inf. Theory 62(8), 4575\u20134588 (2016). doi:\n10.1109\/TIT.2016.2582176","journal-title":"IEEE Trans. Inf. Theory"},{"key":"303_CR22","first-page":"609","volume":"10","author":"P Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. Infinite Finite sets 10, 609\u2013627 (1975)","journal-title":"Infinite Finite sets"},{"key":"303_CR23","doi-asserted-by":"crossref","unstructured":"Franklin, M., Gelles, R., Ostrovsky, R., Schulman, L.J.: Optimal coding for streaming authentication and interactive communication. In: Advances in Cryptology\u2013CRYPTO 2013, LNCS, vol. 8043, pp. 258\u2013276. Springer (2013)","DOI":"10.1007\/978-3-642-40084-1_15"},{"issue":"1","key":"303_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1109\/TIT.2014.2367094","volume":"61","author":"M Franklin","year":"2015","unstructured":"Franklin, M., Gelles, R., Ostrovsky, R., Schulman, L.J.: Optimal coding for streaming authentication and interactive communication. IEEE Trans. Inf. Theory 61(1), 133\u2013145 (2015). doi:\n10.1109\/TIT.2014.2367094","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"303_CR25","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1109\/18.2626","volume":"34","author":"R Gallager","year":"1988","unstructured":"Gallager, R.: Finding parity in a simple broadcast network. IEEE Trans. Inf. Theory 34(2), 176\u2013180 (1988). doi:\n10.1109\/18.2626","journal-title":"IEEE Trans. Inf. Theory"},{"key":"303_CR26","unstructured":"Gelles, R.: Coding for interactive communication: a survey (2015). \nhttp:\/\/www.eng.biu.ac.il\/~gellesr\/survey.pdf"},{"key":"303_CR27","doi-asserted-by":"crossref","unstructured":"Gelles, R., Haeupler, B.: Capacity of interactive communication over erasure channels and channels with feedback. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201915, pp. 1296\u20131311 (2015)","DOI":"10.1137\/1.9781611973730.86"},{"key":"303_CR28","doi-asserted-by":"crossref","unstructured":"Gelles, R., Moitra, A., Sahai, A.: Efficient and explicit coding for interactive communication. In: Proceeding of the IEEE Symposium on Foundations of Computer Science, FOCS \u201911, pp. 768\u2013777 (2011)","DOI":"10.1109\/FOCS.2011.51"},{"issue":"3","key":"303_CR29","doi-asserted-by":"publisher","first-page":"1899","DOI":"10.1109\/TIT.2013.2294186","volume":"60","author":"R Gelles","year":"2014","unstructured":"Gelles, R., Moitra, A., Sahai, A.: Efficient coding for interactive communication. IEEE Trans. Inf. Theory 60(3), 1899\u20131913 (2014). doi:\n10.1109\/TIT.2013.2294186","journal-title":"IEEE Trans. Inf. Theory"},{"key":"303_CR30","doi-asserted-by":"publisher","unstructured":"Gelles, R., Sahai, A., Wadia, A.: Private interactive communication across an adversarial channel. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS \u201914, pp. 135\u2013144. ACM (2014). doi:\n10.1145\/2554797.2554812","DOI":"10.1145\/2554797.2554812"},{"key":"303_CR31","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Haeupler, B.: Optimal Error Rates for interactive coding II: efficiency and list decoding. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS \u201914, pp. 394\u2013403 (2014)","DOI":"10.1109\/FOCS.2014.49"},{"key":"303_CR32","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B., Sudan, M.: Optimal error rates for interactive coding I: adaptivity and other settings. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 794\u2013803. ACM, New York, NY, USA (2014). doi:\n10.1145\/2591796.2591872","DOI":"10.1145\/2591796.2591872"},{"issue":"6","key":"303_CR33","doi-asserted-by":"publisher","first-page":"1806","DOI":"10.1137\/060654864","volume":"37","author":"N Goyal","year":"2008","unstructured":"Goyal, N., Kindler, G., Saks, M.: Lower bounds for the noisy broadcast problem. SIAM J. Comput. 37(6), 1806\u20131841 (2008). doi:\n10.1137\/060654864","journal-title":"SIAM J. Comput."},{"key":"303_CR34","doi-asserted-by":"publisher","unstructured":"Guruswami, V., Indyk, P.: Linear-time encodable\/decodable codes with near-optimal rate. IEEE Trans. Inf. Theory 51(10), 3393\u20133400 (2005). doi:\n10.1109\/TIT.2005.855587","DOI":"10.1109\/TIT.2005.855587"},{"key":"303_CR35","doi-asserted-by":"crossref","unstructured":"Haeupler, B.: Interactive channel capacity revisited. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS \u201914, pp. 226\u2013235 (2014)","DOI":"10.1109\/FOCS.2014.32"},{"key":"303_CR36","doi-asserted-by":"publisher","unstructured":"Hoza, W.M., Schulman, L.J.: The adversarial noise threshold for distributed protocols. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 240\u2013258 (2016). doi:\n10.1137\/1.9781611974331.ch18","DOI":"10.1137\/1.9781611974331.ch18"},{"key":"303_CR37","doi-asserted-by":"crossref","unstructured":"Jain, A., Kalai, Y.T., Lewko, A.: Interactive coding for multiparty protocols. In: Proceedings of the 6th Conference on Innovations in Theoretical Computer Science, ITCS \u201915, pp. 1\u201310 (2015)","DOI":"10.1145\/2688073.2688109"},{"key":"303_CR38","doi-asserted-by":"publisher","unstructured":"Kol, G., Raz, R.: Interactive channel capacity. In: STOC \u201913: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pp. 715\u2013724. ACM, New York, NY, USA (2013). doi:\n10.1145\/2488608.2488699","DOI":"10.1145\/2488608.2488699"},{"key":"303_CR39","doi-asserted-by":"publisher","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC \u201913, pp. 42\u201350. ACM, New York, NY, USA (2013). doi:\n10.1145\/2484239.2501983","DOI":"10.1145\/2484239.2501983"},{"issue":"2","key":"303_CR40","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1667053.1667060","volume":"57","author":"RA Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz local lemma. J. ACM 57(2), 11:1\u201311:15 (2010). doi:\n10.1145\/1667053.1667060","journal-title":"J. ACM"},{"key":"303_CR41","unstructured":"Pankratov, D.: On the power of feedback in interactive channels. [Online:] \nhttp:\/\/people.cs.uchicago.edu\/~pankratov\/papers\/feedback.pdf\n\n (2013)"},{"key":"303_CR42","unstructured":"Rajagopalan, S.: A coding theorem for distributed computation. Ph.D. thesis, University of California at Berkeley, Berkeley, CA, USA (1994). UMI Order No. GAX95-29464"},{"key":"303_CR43","doi-asserted-by":"publisher","unstructured":"Rajagopalan, S., Schulman, L.: A coding theorem for distributed computation. In: STOC \u201994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 790\u2013799. ACM, New York, NY, USA (1994). doi:\n10.1145\/195058.195462","DOI":"10.1145\/195058.195462"},{"key":"303_CR44","doi-asserted-by":"publisher","unstructured":"Schulman, L.J.: Communication on noisy channels: a coding theorem for computation. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 724\u2013733 (1992). doi:\n10.1109\/SFCS.1992.267778","DOI":"10.1109\/SFCS.1992.267778"},{"key":"303_CR45","doi-asserted-by":"publisher","unstructured":"Schulman, L.J.: Deterministic coding for interactive communication. In: STOC \u201993: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 747\u2013756. ACM, New York (1993). doi:\n10.1145\/167088.167279","DOI":"10.1145\/167088.167279"},{"issue":"6","key":"303_CR46","doi-asserted-by":"publisher","first-page":"1745","DOI":"10.1109\/18.556671","volume":"42","author":"LJ Schulman","year":"1996","unstructured":"Schulman, L.J.: Coding for interactive communication. IEEE Trans. Inf. Theory 42(6), 1745\u20131756 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"303_CR47","unstructured":"Shannon, C.E.: A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review 5(1), 3\u201355 (2001). [Originally appeared in Bell System Tech. J. 27, 379\u2013423, 623\u2013656, 1948]"},{"key":"303_CR48","doi-asserted-by":"publisher","unstructured":"Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC \u201995, pp. 388\u2013397. ACM, New York (1995). doi:\n10.1145\/225058.225165","DOI":"10.1145\/225058.225165"},{"key":"303_CR49","unstructured":"Tikhomirov, K., Youssef, P.: The spectral gap of dense random regular graphs. arXiv preprint \narXiv:1610.01765\n\n (2016)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0303-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0303-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0303-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T11:00:48Z","timestamp":1589626848000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0303-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,27]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["303"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0303-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,27]]},"assertion":[{"value":"7 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}