{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T06:40:58Z","timestamp":1788417658015,"version":"build-2803163510"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1527110"],"award-info":[{"award-number":["CCF-1527110"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618280"],"award-info":[{"award-number":["CCF-1618280"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We consider interactive communication performed over two types of noisy channels: binary error channels with noiseless feedback and binary erasure channels. In both cases, the noise model is adversarial. Assuming at most $\\varepsilon$-fraction of the bits can be corrupted, we show coding schemes that simulate any alternating interactive protocol with rate $1-\\Theta(H(\\varepsilon))$. All our simulations are simple, randomized, and computationally efficient. The rates of our coding schemes stand in contrast to the interactive communication rates supported by random or adversarial error channels without feedback, for which the best known coding schemes achieve rates of $1-\\Theta(\\sqrt{\\varepsilon})$ and $1-\\Theta(\\sqrt{\\varepsilon \\log \\log 1\/\\varepsilon})$, respectively. As these rates are conjectured to be optimal, our result implies a large asymptotic gap between interactive communication rates over noisy channels with and without feedback. Such a gap has no equivalent in the standard one-way communication setting.<\/jats:p>","DOI":"10.1137\/15m1052202","type":"journal-article","created":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T16:00:37Z","timestamp":1502985637000},"page":"1449-1472","source":"Crossref","is-referenced-by-count":13,"title":["Capacity of Interactive Communication over Erasure Channels and Channels with Feedback"],"prefix":"10.1137","volume":"46","author":[{"given":"Ran","family":"Gelles","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"atypb1","first-page":"595","author":"Agrawal S.","year":"2016","journal-title":"NJ"},{"key":"atypb2","first-page":"165","author":"Alon N.","year":"2016","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Braverman, K. Efremenko, R. Gelles, and B. Haeupler,\n                      Reliable communication over highly connected noisy networks\n                      , Distrib. Comput., 2017,https:\/\/doi.org\/10.1007\/s00446-017-0303-5.","DOI":"10.1007\/s00446-017-0303-5"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"atypb5","first-page":"160","author":"Brakerski Z.","year":"2012","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2661628"},{"key":"atypb7","first-page":"443","author":"Brakerski Z.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"G. Brassard, A. Nayak, A. Tapp, D. Touchette, and F. Unger,\n                      Noisy interactive quantum communication\n                      , in Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science FOCS, 2014, IEEE, Piscataway, NJ, 2014, pp. 296-305,https:\/\/doi.org\/10.1109\/FOCS.2014.39.","DOI":"10.1109\/FOCS.2014.39"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. Braverman and K. Efremenko,\n                      List and unique coding for interactive communication in the presence of adversarial noise\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS 2014, IEEE, Piscataway, NJ, 2014, pp. 236-245.","DOI":"10.1109\/FOCS.2014.33"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897563"},{"key":"atypb11","first-page":"61","volume":"55","author":"Braverman M.","year":"2016","journal-title":"Leibniz Int. Proc. Inform."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2353994"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"K.M. Chung, R. Pass, and S. Telang,\n                      Knowledge-preserving interactive coding\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS '13, IEEE, Piscataway, NJ, 2013, pp. 449-458.","DOI":"10.1109\/FOCS.2013.55"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2582176"},{"key":"atypb15","first-page":"258","author":"Franklin M.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2367094"},{"key":"atypb17","unstructured":"R. Gelles,\n                      Coding for Interactive Communication: A Survey\n                      ,http:\/\/www.eng.biu.ac.il\/~gellesr\/survey.pdf(2015)."},{"key":"atypb18","first-page":"1296","author":"Gelles R.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb19","first-page":"1922","author":"Gelles R.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb20","first-page":"768","author":"Gelles R.","year":"2011","journal-title":"NJ"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2294186"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2483323"},{"key":"atypb23","first-page":"394","author":"Ghaffari M.","year":"2014","journal-title":"NJ"},{"key":"atypb24","first-page":"794","author":"Ghaffari M.","year":"2014","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"atypb26","first-page":"226","author":"Haeupler B.","year":"2014","journal-title":"NJ"},{"key":"atypb27","first-page":"881","author":"Haeupler B.","year":"2015","journal-title":"Germany"},{"key":"atypb28","first-page":"2123","author":"Haeupler B.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb29","first-page":"715","author":"Kol G.","year":"2013","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"atypb31","unstructured":"D. Pankratov,\n                      On the Power of Feedback in Interactive Channels\n                      ,http:\/\/people.cs.uchicago.edu\/ pankratov\/papers\/feedback.pdf(2013)."},{"key":"atypb32","first-page":"790","author":"Rajagopalan S.","year":"1994","journal-title":"New York"},{"key":"atypb33","first-page":"724","author":"Schulman L. J.","year":"1992","journal-title":"NJ"},{"key":"atypb34","first-page":"747","author":"Schulman L. J.","year":"1993","journal-title":"New York"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056798"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/584091.584093"},{"key":"atypb38","first-page":"739","volume":"117","author":"Varshamov R. R.","year":"1957","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"atypb39","first-page":"209","author":"A.","year":"1979","journal-title":"New York"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1052202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:22:27Z","timestamp":1787340147000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1052202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1052202"],"URL":"https:\/\/doi.org\/10.1137\/15m1052202","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}