{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:06:30Z","timestamp":1775581590655,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006461","name":"Citi Foundation, Citigroup","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"IMOS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,12,17]]},"abstract":"<jats:p>\n            Consider two parties who wish to communicate in order to execute some interactive protocol \u03c0. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of \u03c0 (which was designed for an error-free channel). If \u03c0 only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to\n            <jats:italic>interactive protocols<\/jats:italic>\n            consisting of many short messages.\n          <\/jats:p>\n          <jats:p>\n            Schulman [1992, 1993] introduced the notion of\n            <jats:italic>interactive coding<\/jats:italic>\n            : A simulator that, given any protocol \u03c0, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of \u03c0 (which we denote by\n            <jats:italic>N<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(\n            <jats:italic>N<\/jats:italic>\n            ), has failure probability roughly 2\n            <jats:sup>\n              -\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            , and is resilient to 1\/32-fraction of adversarial error. The second runs in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            log\n            <jats:italic>N<\/jats:italic>\n            ), has failure probability roughly 2\n            <jats:sup>\n              -\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            , and is resilient to some constant fraction of adversarial error. The third runs in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            ), has failure probability 1\/poly(\n            <jats:italic>N<\/jats:italic>\n            ), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made\n            <jats:italic>deterministic<\/jats:italic>\n            if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance).\n          <\/jats:p>","DOI":"10.1145\/2661628","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Fast Interactive Coding against Adversarial Noise"],"prefix":"10.1145","volume":"61","author":[{"given":"Zvika","family":"Brakerski","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yael Tauman","family":"Kalai","sequence":"additional","affiliation":[{"name":"Microsoft Research, New-England"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Shweta Agrawal Ran Gelles and Amit Sahai. 2013. Adaptive protocols for interactive communication. CoRR abs\/1312.4182.  Shweta Agrawal Ran Gelles and Amit Sahai. 2013. Adaptive protocols for interactive communication. CoRR abs\/1312.4182."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_2_1_3_1","unstructured":"Noga Alon and Joel Spencer. 1992. The Probabilistic Method. Wiley.  Noga Alon and Joel Spencer. 1992. The Probabilistic Method. Wiley."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646759.705850"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Manuel Blum William S. Evans Peter Gemmell Sampath Kannan and Moni Naor. 1994. Checking the correctness of memories. Algorithmica 12 2\/3 225--244.  Manuel Blum William S. Evans Peter Gemmell Sampath Kannan and Moni Naor. 1994. Checking the correctness of memories. Algorithmica 12 2\/3 225--244.","DOI":"10.1007\/BF01185212"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090250"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993659"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.55"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.51"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Ran Gelles and Amit Sahai. 2011. Potent tree codes and their applications: Coding for interactive communication revisited. CoRR abs\/1104.0739.  Ran Gelles and Amit Sahai. 2011. Potent tree codes and their applications: Coding for interactive communication revisited. CoRR abs\/1104.0739.","DOI":"10.1109\/FOCS.2011.51"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554812"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/188105.188181"},{"key":"e_1_2_1_13_1","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2013. Optimal error rates for interactive coding II: Efficiency and list decoding. CoRR abs\/1312.1763 (2013).  Mohsen Ghaffari and Bernhard Haeupler. 2013. Optimal error rates for interactive coding II: Efficiency and list decoding. CoRR abs\/1312.1763 (2013)."},{"key":"e_1_2_1_14_1","unstructured":"Mohsen Ghaffari Bernhard Haeupler and Madhu Sudan. 2013. Optimal error rates for interactive coding I: Adaptivity and other settings. CoRR abs\/1312.1764 (2013).  Mohsen Ghaffari Bernhard Haeupler and Madhu Sudan. 2013. Optimal error rates for interactive coding I: Adaptivity and other settings. CoRR abs\/1312.1764 (2013)."},{"key":"e_1_2_1_15_1","volume-title":"Electron. Colloq. Computat. Complex. 4, 20","author":"Goldreich Oded","year":"1997"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488699"},{"key":"e_1_2_1_20_1","volume-title":"Electron. Colloq. Computat. Complex. (ECCC) 18","author":"Moitra Ankur","year":"2011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.921691"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/882494.884425"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796583"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267778"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167279"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225165"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661628","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2661628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:15Z","timestamp":1750231695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12,17]]}},"alternative-id":["10.1145\/2661628"],"URL":"https:\/\/doi.org\/10.1145\/2661628","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,17]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}