 Google Scholar |
 DBLP |
Monographs
- Coding for Interactive Communication: A Survey, [pdf]
Foundations and Trends® in Theoretical Computer Science, 13(1-2), pages 1-157, 2017.I keep updating the tables of Appendix B summarizing the known Interactive-communication schemes. See latest update: [pdf]
Journal Papers
- The Topology of Randomized Symmetry-Breaking Distributed Computing
Pierre Fraigniaud, Ran Gelles, Zvi Lotker
Journal of Applied and Computational Topology, 8, pages 909–940, 2024 - Distributed Computations in Fully-Defective Networks
Keren Censor-Hillel, Shir Cohen, Ran Gelles, Gal Sela
Distributed Computing, 36, pages 501–528, 2023 - Noisy Beeping Networks
Information and Computation, 289(A), pages 104925:1–16, 2022 - Optimal Short-Circuit Resilient Formulas
Journal of the ACM, 69(4), pages 26:1–26:37, 2022 - Efficient Multiparty Interactive Coding—Part II: Non-Oblivious Noise
IEEE Trans. on Information Theory, 68(7), pages 4723-4749, 2022 - Multiparty Interactive Coding Over Networks of Intersecting Broadcast Links
IEEE Journal on Selected Areas in Information Theory, 2(4), pages 1078-1092, 2021
Special Issue: “Beyond Errors and Erasures: Coding for Data Management and Delivery in Networks” - Efficient Multiparty Interactive Coding—Part I: Oblivious Insertions, Deletions and Substitutions
IEEE Trans. on Information Theory, 67(6), pages 3411–3437, 2021
Special Issue: “From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein” - Efficient Error-Correcting Codes for Sliding Windows
SIAM Journal on Discrete Mathematics, 34(1), pages 904–937, 2020 - Reliable Communication over Highly Connected Noisy Networks
Distributed Computing, 32(6), pages 505–515, 2019
Special Issue for PODC'16 (invited) - Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
Distributed Computing, 32(5), pages 405–421, 2019 - Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks
IEEE Trans. on Information Theory, 65(6), pages 3812–3829, 2019 - Explicit Capacity Approaching Coding for Interactive Communication
IEEE Trans. on Information Theory, 64(10), pages 6546–6560, 2018 - Constant-rate coding for multiparty interactive communication is impossible
Journal of the ACM, 65(1), pages 4:1–4:41, 2018 - Coding for Interactive Communication Correcting Insertions and Deletions
IEEE Trans. on Information Theory, 63(10), pages 6256–6270, 2017 - Capacity of Interactive Communication over Erasure Channels and Channels with Feedback
Bernhard Haeupler
SIAM Journal on Computing, 46(4), pages 1449–1472, 2017 - Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
IEEE Trans. on Information Theory, 62(8), pages 4575–4588, 2016 - Private Interactive Communication Across an Adversarial Channel
IEEE Trans. on Information Theory, 61(12), pages 6860–6875, 2015 - Optimal Coding for Streaming Authentication and Interactive Communication
IEEE Trans. on Information Theory, 61(1), pages 133–145, 2015 - Efficient Coding for Interactive Communication
IEEE Trans. on Information Theory, 60(3), pages 1899–1913, 2014 - How to catch L2-Heavy Hitters on Sliding Windows
Theoretical Computer Science, 554, pages 82–94, 2014.
Special Issue for COCOON'13 (invited) - Attacks on Fixed Apparatus Quantum Key Distribution Schemes
Physical Review A, (90):012329, 2014 - Position-Based Quantum Cryptography: Impossibility and Constructions,
,
SIAM Journal on Computing, 43(1), pages 150–178, 2014
Selected as a plenary talk at QIP 2011. Reviewed in Nature's "News and Views" column (G. Brassard 2011) - Security and Composability of Randomness Expansion from Bell Inequalities
Physical Review A, (87):012335, 2013 - Security of the Bennett-Brassard Quantum Key Distribution Protocol Against Collective Attacks
Algorithms, 2(2), pages 790–807, 2009 - Semiquantum Key Distribution
Physical Review A, (79):032341, 2009
(recent) Conference Papers
- Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary
Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, Francois Taiani, Vassilis Zikas
OPODIS'24 (also: Brief Announcement in DISC'24), [arXiv:2312.16253] - Sorting in One and Two Rounds using t-Comparators
Ran Gelles, Zvi Lotker, Frederick Malmann-Trenn
DISC'24, [arXiv:2405.12678] - Content-Oblivious Leader Election on Rings
Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin
DISC'24, [arXiv:2405.03646] - Interactive Coding with Unbounded Noise
Eden Fargion, Ran Gelles, Meghal Gupta
RANDOM'24, [arXiv:2407.09463] - Brief Announcement: Content-Oblivious Leader Election on Rings
Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin
PODC'24, [arXiv:2405.03646] - Information Exchange is Harder with Noise at Source
Manuj Mukherjee, Ran Gelles
ISIT'24 - Computation in Server-Assisted Noisy Networks
Manuj Mukherjee, Ran Gelles
ISIT'24 - Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Fabien Dufoulon, Yuval Emek, Ran Gelles
ITCS'23, [arXiv:2210.06882] - Distributed Computations in Fully-Defective Networks
Keren Censor-Hillel, Shir Cohen, Ran Gelles, Gal Sela
PODC'22, [arXiv:2205.11148] - Multiparty Interactive Communication with Broadcast Links
Manuj Mukherjee, Ran Gelles
ITW'21, [arXiv:2105.01506] - The Topology of Randomized Symmetry-Breaking Distributed Computing
Pierre Fraigniaud, Ran Gelles, Zvi Lotker
PODC'21, [arXiv:2105.11713]