Google Scholar  DBLP

Monographs

  • Coding for Interactive Communication: A Survey, [pdf]
    Ran Gelles

    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

  1. Efficient Multiparty Interactive Coding—Part I: Oblivious Insertions, Deletions and Substitutions
    Ran Gelles, Yael T. Kalai, Govind Ramnarayan
    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”
  2. Efficient Error-Correcting Codes for Sliding Windows
    Ran Gelles, Rafail Ostrovsky, Alan Roytman
    SIAM Journal on Discrete Mathematics, 34(1), pages 904–937, 2020
  3. Reliable Communication over Highly Connected Noisy Networks
    Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
    Distributed Computing, 32(6), pages 505–515, 2019
    Special Issue for PODC'16 (invited)
  4. Making Asynchronous Distributed Computations Robust to Noise
    Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
    Distributed Computing, 32(5), pages 405–421, 2019
  5. Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks
    Ran Gelles, Yael T. Kalai
    IEEE Trans. on Information Theory, 65(6), pages 3812–3829, 2019
  6. Explicit Capacity Approaching Coding for Interactive Communication
    Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
    IEEE Trans. on Information Theory, 64(10), pages 6546–6560, 2018
  7. Constant-rate coding for multiparty interactive communication is impossible
    Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
    Journal of the ACM, 65(1), pages 4:1–4:41, 2018
  8. Coding for Interactive Communication Correcting Insertions and Deletions
    Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
    IEEE Trans. on Information Theory, 63(10), pages 6256–6270, 2017
  9. Capacity of Interactive Communication over Erasure Channels and Channels with Feedback
    Ran Gelles, Bernhard Haeupler
    SIAM Journal on Computing, 46(4), pages 1449–1472, 2017
  10. Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
    Klim Efremenko, Ran Gelles, Bernhard Haeupler
    IEEE Trans. on Information Theory, 62(8), pages 4575–4588, 2016
  11. Private Interactive Communication Across an Adversarial Channel
    Ran Gelles, Amit Sahai, Akshay Wadia
    IEEE Trans. on Information Theory, 61(12), pages 6860–6875, 2015
  12. Optimal Coding for Streaming Authentication and Interactive Communication
    Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman
    IEEE Trans. on Information Theory, 61(1), pages 133–145, 2015
  13. Efficient Coding for Interactive Communication
    Ran Gelles, Ankur Moitra, Amit Sahai
    IEEE Trans. on Information Theory, 60(3), pages 1899–1913, 2014
  14. How to catch L2-Heavy Hitters on Sliding Windows
    Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
    Theoretical Computer Science, 554, pages 82–94, 2014.
    Special Issue for COCOON'13 (invited)
  15. Attacks on Fixed Apparatus Quantum Key Distribution Schemes
    Michel Boyer, Ran Gelles, Tal Mor
    Physical Review A, (90):012329, 2014
  16. Position-Based Quantum Cryptography: Impossibility and Constructions,
    Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner,
    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)
  17. Security and Composability of Randomness Expansion from Bell Inequalities
    Serge Fehr, Ran Gelles, Christian Schaffner
    Physical Review A, (87):012335, 2013
  18. Security of the Bennett-Brassard Quantum Key Distribution Protocol Against Collective Attacks
    Michel Boyer, Ran Gelles, Tal Mor
    Algorithms, 2(2), pages 790–807, 2009
  19. Semiquantum Key Distribution
    Michel Boyer, Ran Gelles, Dan Kenigsberg, Tal Mor
    Physical Review A, (79):032341, 2009

(recent) Conference Papers

  • 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]
  • Noisy Beeping Networks
    Yagel Ashkenazi, Ran Gelles, Amir Leshem
    PODC'20 (Brief Announcement), [arXiv:1909.06811]
  • Interactive coding resilient to an unknown number of erasures
    Ran Gelles, Siddharth V. Iyer
    OPODIS'19, [arXiv:1811.02527]
  • Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
    Ran Gelles, Yael Kalai, Govind Ramnarayan
    PODC'19, [arXiv:1901.09863]
  • Optimal Short-Circuit Resilient Formulas
    Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
    CCC'19, [arXiv:1807.05014]
  • Secure Two-Party Computation over Unreliable Channels
    Ran Gelles, Anat Paskin-Cherniavsky, Vassilis Zikas
    SCN'2018, [eprint 2018/506]
  • Making Asynchronous Distributed Computations Robust to Noise
    Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
    ITCS'18, [arXiv:1702.07403]