Publications

Conference Papers

2020

  1. STOC
    Optimally Resilient Codes for List-Decoding from Insertions and Deletions
    Guruswami, V., Haeupler, B., and Shahrasbi, A.
    In Proceedings of the ACM Symposium on Theory of Computing (STOC) 2020

2019

  1. STOC
    Near-Linear Time Insertion-Deletion Codes and (1+\(\varepsilon\))-Approximating Edit Distance via Indexing
    Haeupler, B., Rubinstein, A., and Shahrasbi, A.
    In Proceedings of the ACM Symposium on Theory of Computing (STOC) 2019
  2. SODA
    Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
    Cheng, K., Haeupler, B., Li, X., Shahrasbi, A., and Wu, K.
    In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019

2018

  1. ICALP
    Synchronization Strings: List Decoding for Insertions and Deletions
    Haeupler, B., Shahrasbi, A., and Sudan, M.
    In Proceedings of the International Conference on Automata, Languages, and Programming (ICALP) 2018
  2. STOC
    Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
    Haeupler, B., and Shahrasbi, A.
    In Proceedings of the ACM Symposium on Theory of Computing (STOC) 2018
  3. ICALP
    Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
    Haeupler, B., Shahrasbi, A., and Vitercik, E.
    In Proceedings of the International Conference on Automata, Languages, and Programming (ICALP) 2018

2017

  1. STOC
    Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
    Haeupler, B., and Shahrasbi, A.
    In Proceedings of the ACM Symposium on Theory of Computing (STOC) 2017
    Invited to be published in the Theory of Computing journal

2014

  1. ISIT
    Critical Graphs in Index Coding
    Tahmasbi, M., Shahrasbi, A., and Gohari, A.
    In IEEE International Symposium on Information Theory (ISIT) 2014


Journal Papers

2021

  1. IEEE Trans.
    Inf. Theory
    Synchronization Strings and Codes for Insertions and Deletions – a Survey
    Haeupler, B., and Shahrasbi, A.
    IEEE Transactions of Information Theory, 2021
    Invited to IEEE Transactions on Information Theory: Special Issue Dedicated to the Memory of Vladimir I. Levenshtein
  2. JACM
    Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
    Haeupler, B., and Shahrasbi, A.
    Journal of the ACM, 2021

2014

  1. JSAC
    Critical graphs in Index Coding
    Tahmasbi, M., Shahrasbi, A., and Gohari, A.
    IEEE Journal on Selected areas in Communications, 2014


Manuscripts

2020

  1. Ph.D. Thesis
    Coding for Synchronization Errors
    Shahrasbi, A.
    2020
  2. Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes
    Haeupler, B., and Shahrasbi, A.
    2020