{"id":29,"date":"2016-10-10T11:35:36","date_gmt":"2016-10-10T08:35:36","guid":{"rendered":"http:\/\/www.eng.biu.ac.il\/gellesr\/?page_id=29"},"modified":"2025-09-04T10:37:48","modified_gmt":"2025-09-04T07:37:48","slug":"publications","status":"publish","type":"page","link":"https:\/\/www.eng.biu.ac.il\/gellesr\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"\n<table style=\"border-collapse: collapse;width: 100%;height: 41px\">\n<tbody>\n<tr style=\"height: 41px\">\n<td style=\"width: 50%;height: 41px\"><a href=\"https:\/\/scholar.google.co.il\/citations?user=BGPDtPEAAAAJ\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-506\" src=\"http:\/\/www.eng.biu.ac.il\/gellesr\/files\/2025\/09\/Google_Scholar_blue_logo-291x300.png\" alt=\"\" width=\"98\" height=\"101\" \/><\/a><\/td>\n<td style=\"width: 50%;height: 41px\"><a href=\"https:\/\/dblp.org\/pid\/88\/8575.html\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-505 aligncenter\" src=\"http:\/\/www.eng.biu.ac.il\/gellesr\/files\/2025\/09\/dblp-1.png\" alt=\"\" width=\"109\" height=\"70\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>Monographs<\/h3>\n<p><a href=\"http:\/\/dx.doi.org\/10.1561\/0400000079\" target=\"_blank\" rel=\"noopener noreferrer\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-119 size-full\" src=\"http:\/\/www.eng.biu.ac.il\/gellesr\/files\/2016\/10\/9781680833461.jpg\" alt=\"\" width=\"141\" height=\"212\" \/><\/a><\/p>\n<ul>\n<li><span style=\"font-size: large\">Coding for Interactive Communication: A Survey, <a href=\"http:\/\/www.eng.biu.ac.il\/~gellesr\/survey.pdf\"> [pdf]<\/a><br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles<\/span><\/span><br \/><em>Foundations and Trends\u00ae in Theoretical Computer Science<\/em>, 13(1-2), pages 1-157, 2017.\n<p>\u00a0<\/p>\n<p>I keep updating the tables of Appendix B summarizing the known Interactive-communication schemes. See latest update: <a href=\"http:\/\/www.eng.biu.ac.il\/gellesr\/files\/2022\/11\/IC-schemes.pdf\">[pdf]<\/a><\/p>\n<\/li>\n<\/ul>\n<h3>\u00a0Journal Papers<\/h3>\n<ol>\n<li>The Topology of Randomized Symmetry-Breaking Distributed Computing<br \/><span style=\"color: #999999\">Pierre Fraigniaud, Ran Gelles, Zvi Lotker<\/span><br \/><em>Journal of Applied and Computational Topology<\/em>, 8, pages 909\u2013940, 2024<\/li>\n<li>Distributed Computations in Fully-Defective Networks<br \/><span style=\"color: #999999\">Keren Censor-Hillel, Shir Cohen, Ran Gelles, Gal Sela<br \/><\/span><em>Distributed Computing<\/em>, 36, pages 501\u2013528, 2023<\/li>\n<li>Noisy Beeping Networks<br \/><span class=\"authors\" style=\"color: #999999\"> Yagel Ashkenazi, Ran Gelles, Amir Leshem<\/span><br \/><em>Information and Computation,<\/em>\u00a0289(A), pages 104925:1\u201316, 2022<\/li>\n<li>Optimal Short-Circuit Resilient Formulas<br \/><span class=\"authors\" style=\"color: #999999\"> Mark Braverman, Klim Efremenko, Ran Gelles, Michael Yitayew<\/span><br \/><em>Journal of the ACM,<\/em> 69(4), pages 26:1\u201326:37, 2022<\/li>\n<li>Efficient Multiparty Interactive Coding\u2014Part II: Non-Oblivious Noise<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Yael T. Kalai, Govind Ramnarayan<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 68(7), pages 4723-4749, 2022<\/li>\n<li>Multiparty Interactive Coding Over Networks of Intersecting Broadcast Links<br \/><span class=\"authors\" style=\"color: #999999\">Manuj Mekherjee, Ran Gelles<\/span><br \/><em>IEEE Journal on Selected Areas in Information Theory<\/em>, 2(4), pages 1078-1092, 2021<br \/><small>Special Issue: \u201cBeyond Errors and Erasures: Coding for Data Management and Delivery in Networks\u201d<\/small><\/li>\n<li>Efficient Multiparty Interactive Coding\u2014Part I: Oblivious Insertions, Deletions and Substitutions<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Yael T. Kalai, Govind Ramnarayan<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 67(6), pages 3411\u20133437, 2021<br \/><small>Special Issue: \u201cFrom Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein\u201d<\/small><\/li>\n<li>Efficient Error-Correcting Codes for Sliding Windows<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Rafail Ostrovsky, Alan Roytman<\/span><br \/><em>SIAM Journal on Discrete Mathematics<\/em>, 34(1), pages 904\u2013937, 2020<\/li>\n<li>Reliable Communication over Highly Connected Noisy Networks<br \/><span class=\"authors\" style=\"color: #999999\">Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler<\/span><br \/><em>Distributed Computing<\/em>, 32(6), pages 505\u2013515, 2019<br \/><small>Special Issue for PODC'16 <span class=\"where\">(<span style=\"color: #ff0000\">invited<\/span>)<\/span><\/small><\/li>\n<li>Making Asynchronous Distributed Computations Robust to Noise<br \/><span style=\"color: #999999\">Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler<\/span><br \/><em>Distributed Computing<\/em>, 32(5), pages 405\u2013421, 2019<\/li>\n<li>Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Yael T. Kalai<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 65(6), pages 3812\u20133829, 2019<\/li>\n<li>Explicit Capacity Approaching Coding for Interactive Communication<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 64(10), pages 6546\u20136560, 2018<\/li>\n<li>Constant-rate coding for multiparty interactive communication is impossible<br \/><span class=\"authors\" style=\"color: #999999\"> Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler<\/span><br \/><em>Journal of the ACM,<\/em> 65(1), pages 4:1\u20134:41, 2018<\/li>\n<li>Coding for Interactive Communication Correcting Insertions and Deletions<br \/><span class=\"authors\" style=\"color: #999999\">Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 63(10), pages 6256\u20136270, 2017<\/li>\n<li>Capacity of Interactive Communication over Erasure Channels and Channels with Feedback<br \/><span style=\"color: #999999\"><span class=\"authors\">Ran Gelles, <\/span>Bernhard Haeupler<\/span><br \/><em>SIAM Journal on Computing,<\/em> 46(4), pages 1449\u20131472, 2017<\/li>\n<li>Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback<br \/><span class=\"authors\" style=\"color: #999999\">Klim Efremenko, Ran Gelles, Bernhard Haeupler<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 62(8), pages 4575\u20134588, 2016<\/li>\n<li>Private Interactive Communication Across an Adversarial Channel<br \/><span class=\"authors\" style=\"color: #999999\">Ran Gelles, Amit Sahai, Akshay Wadia<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 61(12), pages 6860\u20136875, 2015<\/li>\n<li>Optimal Coding for Streaming Authentication and Interactive Communication<br \/><span class=\"authors\" style=\"color: #999999\"> Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 61(1), pages 133\u2013145, 2015<\/li>\n<li>Efficient Coding for Interactive Communication<br \/><span class=\"authors\" style=\"color: #999999\"> Ran Gelles, Ankur Moitra, Amit Sahai<\/span><br \/><em>IEEE Trans. on Information Theory<\/em>, 60(3), pages 1899\u20131913, 2014<\/li>\n<li>How to catch L<sub>2<\/sub>-Heavy Hitters on Sliding Windows<br \/><span class=\"authors\" style=\"color: #999999\"> Vladimir Braverman, Ran Gelles, Rafail Ostrovsky<\/span><br \/><em>Theoretical Computer Science<\/em>, 554, pages 82\u201394, 2014.<br \/><small>Special Issue for COCOON'13 <span class=\"where\">(<span style=\"color: #ff0000\">invited<\/span>)<\/span><\/small><\/li>\n<li>Attacks on Fixed Apparatus Quantum Key Distribution Schemes<br \/><span class=\"authors\" style=\"color: #999999\">Michel Boyer, Ran Gelles, Tal Mor<\/span><br \/><em>Physical Review A<\/em>, (90):012329, 2014<\/li>\n<li>Position-Based Quantum Cryptography: Impossibility and Constructions,<br \/><span class=\"authors\"><span style=\"color: #999999\">Harry<\/span> <span style=\"color: #999999\">Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner<\/span><\/span>,<br \/><em>SIAM Journal on Computing,<\/em> 43(1), pages 150\u2013178, 2014<br \/><small>Selected as a <span style=\"color: #ff0000\">plenary talk<\/span> at QIP 2011. Reviewed in<span style=\"color: #ff0000\"> Nature<\/span>'s \"News and Views\" column (<a href=\"https:\/\/www.nature.com\/nature\/journal\/v479\/n7373\/full\/479307a.html\">G. Brassard 2011<\/a>)<br \/><\/small><\/li>\n<li>Security and Composability of Randomness Expansion from Bell Inequalities<br \/><span class=\"authors\" style=\"color: #999999\">Serge Fehr, Ran Gelles, Christian Schaffner<\/span><br \/><em>Physical Review A<\/em>, (87):012335, 2013<\/li>\n<li>Security of the Bennett-Brassard Quantum Key Distribution Protocol Against Collective Attacks<br \/><span class=\"authors\" style=\"color: #999999\">Michel Boyer, Ran Gelles, Tal Mor<\/span><br \/>Algorithms, 2(2), pages 790\u2013807, 2009<\/li>\n<li>Semiquantum Key Distribution<br \/><span class=\"authors\" style=\"color: #999999\"> Michel Boyer, Ran Gelles, Dan Kenigsberg, Tal Mor<\/span><br \/><em>Physical Review A<\/em>, (79):032341, 2009<\/li>\n<\/ol>\n<h3>(recent) Conference Papers<\/h3>\n<ul type=\"disc\">\n<li><span data-olk-copy-source=\"MessageBody\">Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique<\/span><br \/><span style=\"color: #999999\">Keren Censor-Hillel, Orr Fischer, Ran Gelles, Pedro Soto<\/span><br \/>DISC'25, <a href=\"https:\/\/arxiv.org\/abs\/2508.08740\">[arXiv:2508.08740]<\/a><\/li>\n<li><span data-olk-copy-source=\"MessageBody\">Nearly Optimal Parallel Broadcast in the Plain Public Key Model<\/span><br \/><span style=\"color: #999999\">Ran Gelles, Christoph Lenzen, Julian Loss, Sravya Yandamuri<\/span><br \/>CRYPTO'25, <a href=\"https:\/\/eprint.iacr.org\/2025\/1012\">[ePrint:2025\/1012]<\/a><\/li>\n<li><span data-olk-copy-source=\"MessageBody\">Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary<\/span><br \/><span style=\"color: #999999\">Timoth\u00e9 Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, Francois Taiani, Vassilis Zikas<\/span><br \/>OPODIS'24 (also: Brief Announcement in DISC'24), <a href=\"https:\/\/arxiv.org\/abs\/2312.16253\">[arXiv:2312.16253]<\/a><\/li>\n<li>Sorting in One and Two Rounds using <em>t-<\/em>Comparators<br \/><span style=\"color: #999999\">Ran Gelles, Zvi Lotker, Frederick Malmann-Trenn<\/span><br \/>DISC'24, <a href=\"https:\/\/arxiv.org\/abs\/2405.12678\">[arXiv:2405.12678]<\/a><\/li>\n<li>Content-Oblivious Leader Election on Rings<br \/><span style=\"color: #999999\">Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin<\/span><br \/>DISC'24, <a href=\"https:\/\/arxiv.org\/abs\/2405.03646\">[arXiv:2405.03646]<\/a><\/li>\n<li>Interactive Coding with Unbounded Noise<br \/><span style=\"color: #999999\">Eden Fargion, Ran Gelles, Meghal Gupta<\/span><br \/>RANDOM'24, <a href=\"https:\/\/arxiv.org\/abs\/2407.09463\">[arXiv:2407.09463]<\/a><\/li>\n<li>Brief Announcement: Content-Oblivious Leader Election on Rings<br \/><span style=\"color: #999999\">Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin<\/span><br \/>PODC'24, <a href=\"https:\/\/arxiv.org\/abs\/2405.03646\">[arXiv:2405.03646]<\/a><\/li>\n<li>Information Exchange is Harder with Noise at Source<br \/><span style=\"color: #999999\">Manuj Mukherjee, Ran Gelles<\/span><br \/>ISIT'24<\/li>\n<li>Computation in Server-Assisted Noisy Networks<br \/><span style=\"color: #999999\">Manuj Mukherjee, Ran Gelles<\/span><br \/>ISIT'24<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Monographs Coding for Interactive Communication: A Survey, [pdf]Ran GellesFoundations and Trends\u00ae in Theoretical Computer Science, 13(1-2), pages 1-157, 2017. \u00a0 I keep updating the tables of Appendix B summarizing the known Interactive-communication schemes. See latest update: [pdf] \u00a0Journal Papers The Topology of Randomized Symmetry-Breaking Distributed ComputingPierre Fraigniaud, Ran Gelles, Zvi LotkerJournal of Applied and Computational &hellip; <a href=\"https:\/\/www.eng.biu.ac.il\/gellesr\/publications\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Publications<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-29","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/29"}],"collection":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/comments?post=29"}],"version-history":[{"count":69,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/29\/revisions"}],"predecessor-version":[{"id":511,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/29\/revisions\/511"}],"wp:attachment":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/media?parent=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}