{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T11:14:56Z","timestamp":1760181296519,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,25]],"date-time":"2020-12-25T00:00:00Z","timestamp":1608854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["639573"],"award-info":[{"award-number":["639573"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.<\/jats:p>","DOI":"10.3390\/e23010017","type":"journal-article","created":{"date-parts":[[2020,12,25]],"date-time":"2020-12-25T09:30:19Z","timestamp":1608888619000},"page":"17","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Interactive Capacity of Finite-State Protocols"],"prefix":"10.3390","volume":"23","author":[{"given":"Assaf","family":"Ben-Yishai","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 9190401, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young-Han","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of California, San Diego, La Jolla, CA 92093 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Shayevitz","sequence":"additional","affiliation":[{"name":"Department of EE\u2013Systems, Tel Aviv University, Tel Aviv 6997801, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,25]]},"reference":[{"key":"ref_1","unstructured":"Shannon, C.E. (1960, January 20\u201330). Two-way communication channels. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, the Regents of the University of California, Oakland, CA, USA."},{"key":"ref_2","unstructured":"Gelles, R. (2020, December 24). Coding for Interactive Communication: A Survey. Available online: http:\/\/www.eng.biu.ac.il\/~gellesr\/survey.pdf."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Schulman, L.J. (1992, January 24\u201327). Communication on noisy channels: A coding theorem for computation. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA.","DOI":"10.1109\/SFCS.1992.267778"},{"key":"ref_4","unstructured":"Ben-Yishai, A., Kim, Y.-H., Ordentlich, O., and Shayevitz, O. (2019). A Lower Bound on the Interactive Capacity of Binary Memoryless Symmetric Channels. arXiv."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Haeupler, B., and Velingker, A. (2017, January 16\u201319). Bridging the capacity gap between interactive and one-way communication. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.138"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ben-Yishai, A., Shayevitz, O., and Kim, Y.-H. (2019, January 7\u201312). Shannon Capacity Is Achievable for a Large Class of Interactive Markovian Protocols. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849512"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1745","DOI":"10.1109\/18.556671","article-title":"Coding for interactive communication","volume":"42","author":"Schulman","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","unstructured":"Yao, A.C.C. (May, January 30). Some complexity questions related to distributive computing (preliminary report). Proceedings of the eLeventh Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cover, T.M., and Thomas, J. (2006). Elements of Information Theory, Wiley. [2nd ed.].","DOI":"10.1002\/047174882X"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kol, G., and Raz, R. (2013, January 1\u20134). Interactive channel capacity. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA.","DOI":"10.1145\/2488608.2488699"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Haeupler, B. (2014, January 19\u201321). Interactive channel capacity revisited. Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA.","DOI":"10.1109\/FOCS.2014.32"},{"key":"ref_12","unstructured":"Ghaffari, M., Haeupler, B., and Sudan, M. (June, January 31). Optimal error rates for interactive coding I: Adaptivity and other settings. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Gelles, R., and Sahai, A. (2016, January 10\u201315). Adaptive protocols for interactive communication. Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541368"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2307","DOI":"10.1109\/TIT.2010.2043769","article-title":"Channel coding rate in the finite blocklength regime","volume":"56","author":"Polyanskiy","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","unstructured":"Kushlevitz, E., and Nisan, N. (2006). Communication Complexity, Cambridge University Press."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","article-title":"The probabilistic communication complexity of set intersection","volume":"5","author":"Kalyanasundaram","year":"1992","journal-title":"SIAM J. Discret. Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Razborov, A.A. (1990). On the distributional complexity of disjointness. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/BFb0032036"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","article-title":"An information statistics approach to data stream and communication complexity","volume":"68","author":"Jayram","year":"2004","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"6058","DOI":"10.1109\/TIT.2014.2347282","article-title":"Information equals amortized communication","volume":"60","author":"Braverman","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","unstructured":"Gallager, R.G. (1968). Information Theory and Reliable Communication, John Wiley & Sons."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/17\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:46:04Z","timestamp":1760179564000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,25]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["e23010017"],"URL":"https:\/\/doi.org\/10.3390\/e23010017","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,12,25]]}}}