Publications

2022

1. APPROX

   Sketching Approximability of (Weak) Monarchy Predicates

   Chou, C., Golovnev, A., Shahrasbi, A., Sudan, M., and Velusamy, S.

   In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022

   Abstract arXiv BibTex

   @inproceedings{chou2022sketching,
     title = {Sketching Approximability of (Weak) Monarchy Predicates},
     author = {Chou, Chi-Ning and Golovnev, Alexander and Shahrasbi, Amirbehshad and Sudan, Madhu and Velusamy, Santhoshini},
     arxiv = {2205.02345},
     booktitle = {Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},
     abbr = {APPROX},
     year = {2022}
   }
   

   We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every \(k ≥5\), we show that CSPs where the underlying predicate is a pure monarchy function on \(k\) variables have no non-trivial sketching approximation algorithm in \(o(\sqrt n)\) space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by \(O(\log(n))\) space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs.
   
   Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.

2. ITW

   Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes

   Haeupler, B., and Shahrasbi, A.

   In Proceedings of the IEEE Information Theory Workshop (ITW) 2022

   Abstract arXiv BibTex

   @inproceedings{haeupler-list-dec-capacity2020,
     title = {Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     year = {2022},
     booktitle = {Proceedings of the IEEE Information Theory Workshop (ITW)},
     abbr = {ITW},
     arxiv = {2009.13307}
   }
   

   This paper presents general bounds on the highest achievable rate for list-decodable insertion-deletion codes. In particular, we give novel outer and inner bounds for the highest achievable communication rate of any insertion-deletion code that can be list-decoded from any \(γ\) fraction of insertions and any \(δ\) fraction of deletions. Our bounds simultaneously generalize the known bounds for the previously studied special cases of insertion-only, deletion-only, and zero-rate and correct other bounds that had been reported for the general case.

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

   Abstract arXiv BibTex

   @inproceedings{guruswami2019optimally,
     author = {Guruswami, Venkatesan and Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     title = {Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
     booktitle = {Proceedings of the ACM Symposium on Theory of Computing (STOC)},
     pages = {524--537},
     year = {2020},
     abbr = {STOC},
     arxiv = {1909.10683}
   }
   

   We give a complete answer to the following basic question: "What is the maximal fraction of deletions or insertions tolerable by q-ary list-decodable codes with non-vanishing information rate?"
   This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results was that a \(γ≤0.707\) fraction of insertions is tolerable by some binary code family.
   For any desired \(\varepsilon>0\), we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of \(γ\) fraction of insertions and \(δ\) fraction of deletions as long as \(γ+2δ≤1-\varepsilon\). On the other hand, for any \(γ, δ\) with \(γ+2δ=1\) list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions.
   We further generalize our result to codes over any finite alphabet of size \(q\). Surprisingly, our work reveals that the feasibility region for \(q>2\) is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a \((q-1\))-piece-wise linear boundary whose \(q\) corner-points lie on a quadratic curve.
   The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of \(δ, γ\) within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAM J. Discrete Math; 2014]. Finally we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate.

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

   Abstract arXiv BibTex

   @inproceedings{haeupler2019near,
     title = {Near-Linear Time Insertion-Deletion Codes and (1+\(\varepsilon\))-Approximating Edit Distance via Indexing},
     author = {Haeupler, Bernhard and Rubinstein, Aviad and Shahrasbi, Amirbehshad},
     booktitle = {Proceedings of the ACM Symposium on Theory of Computing (STOC)},
     pages = {697--708},
     year = {2019},
     abbr = {STOC},
     arxiv = {1810.11863}
   }
   

   We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an indexing string \(I\). In particular, for every length \(n\) and every \(\varepsilon >0\), one can in near linear time construct a string \(I ∈Σ’^n\) with \(|Σ’| = O_\varepsilon(1)\), such that, indexing any string \(S ∈Σ^n\), symbol-by-symbol, with \(I\) results in a string \(S’ ∈Σ’^\prime\)^\(n\) where \(Σ’^\prime = Σ\times Σ’\) for which edit distance computations are easy, i.e., one can compute a \((1+\varepsilon)\)-approximation of the edit distance between \(S’\) and any other string in \(O(n⋅polylog(n))\) time. Our indexing schemes can be used to improve the decoding complexity of state-of-the-art error correcting codes for insertion and deletions. In particular, they lead to near-linear time decoding algorithms for the insertion-deletion codes of [Haeupler, Shahrasbi; STOC ’17] and list-decodable insertion-deletion codes of [Haeupler, Shahrasbi, Sudan; ICALP ‘18]. Interestingly, the latter codes are a crucial ingredient in the construction of fast-decodable indexing schemes.

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

   Abstract arXiv BibTex

   @inproceedings{cheng2018synchronization,
     title = {Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets},
     author = {Cheng, Kuan and Haeupler, Bernhard and Li, Xin and Shahrasbi, Amirbehshad and Wu, Ke},
     booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
     pages = {2185--2204},
     year = {2019},
     abbr = {SODA},
     arxiv = {1803.03530}
   }
   

   Synchronization strings are recently introduced by Haeupler and Shahrasbi [STOC 2017] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added.
   Haeupler and Shahrasbi [STOC 2017] showed that for any parameter \(\varepsilon>0\), synchronization strings of arbitrary length exist over an alphabet whose size depends only on \(\varepsilon\). Specifically, Haeupler and Shahrasbi [STOC 2017] obtained an alphabet size of \(O(\varepsilon\)^\(-4\)\()\), which left an open question on where the minimal size of such alphabets lies between \(Ω(\varepsilon\)^\(-1\)\()\) and \(O(\varepsilon\)^\(-4\)\()\). In this work, we partially bridge this gap by providing an improved lower bound of \(Ω(\varepsilon\)^\(-3/2\)\()\), and an improved upper bound of \(O(\varepsilon\)^\(-2\)\()\). We also provide fast explicit constructions of synchronization strings over small alphabets.
   Further, along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant \(\varepsilon < 1\). We show that one can construct \(\varepsilon\)-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.

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

   Abstract arXiv BibTex

   @inproceedings{haeupler2018synchronization4,
     title = {Synchronization Strings: List Decoding for Insertions and Deletions},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad and Sudan, Madhu},
     booktitle = {Proceedings of the International Conference on Automata, Languages, and Programming (ICALP)},
     year = {2018},
     abbr = {ICALP},
     arxiv = {1802.08663}
   }
   

   We study codes that are list-decodable under insertions and deletions ("insdel codes"). Specifically, we consider the setting where, given a codeword \(x\) of length \(n\) over some finite alphabet \(Σ\) of size \(q\), \(δn\) codeword symbols may be adversarially deleted and \(γ⋅n\)symbols may be adversarially inserted to yield a corrupted word \(w\). A code is said to be list-decodable if there is an (efficient) algorithm that, given \(w\), reports a small list of codewords that include the original codeword \(x\). Given \(δ\) and \(γ\) we study what is the rate \(R\) for which there exists a constant \(q\) and list size \(L\) such that there exist codes of rate \(R\) correcting \(δ\)-fraction insertions and \(γ\)-fraction deletions while reporting lists of size at most \(L\).
   Using the concept of synchronization strings, introduced by the first two authors [Proc. STOC 2017], we show some surprising results. We show that for every \(0≤δ< 1\), every \(0 ≤γ< ∞\) and every \(ε> 0\) there exists codes of rate \(1 - δ- ε\) and constant alphabet (so \(q = O_δ,γ,ε(1)\)) and sub-polynomial list sizes. Furthermore our codes are accompanied by efficient (polynomial time) decoding algorithms. We stress that the fraction of insertions can be arbitrarily large (more than 100%), and the rate is independent of this parameter. We also prove several tight bounds on the parameters of list-decodable insdel codes. In particular we show that the alphabet size of insdel codes needs to be exponentially large in \(ε^-\)\(^1\), where \(ε\) is the gap to capacity above. Our result even applies to settings where the unique-decoding capacity equals the list-decoding capacity and when it does so, it shows that the alphabet size needs to be exponentially large in the gap to capacity. This is sharp contrast to the Hamming error model where alphabet size polynomial in \(ε^-\)\(^1\) suffices for unique decoding. This lower bound also shows that the exponential dependence on the alphabet size in previous works that constructed insdel codes is actually necessary!
   Our result sheds light on the remarkable asymmetry between the impact of insertions and deletions from the point of view of error-correction: Whereas deletions cost in the rate of the code, insertion costs are borne by the adversary and not the code! Our results also highlight the dominance of the model of insertions and deletions over the Hamming model: A Hamming error is equal to one insertion and one deletion (at the same location). Thus the effect of \(δ\)-fraction Hamming errors can be simulated by \(δ\)-fraction of deletions and \(δ\)-fraction of insertions — but insdel codes can deal with much more insertions without loss in rate (though at the price of higher alphabet size).

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

   Abstract arXiv BibTex

   @inproceedings{haeupler2017synchronization3,
     title = {Synchronization Strings: Explicit Constructions, Local Decoding, and Applications},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     booktitle = {Proceedings of the ACM Symposium on Theory of Computing (STOC)},
     pages = {841--854},
     year = {2018},
     abbr = {STOC},
     arxiv = {1710.09795}
   }
   

   This paper gives new results for synchronization strings, a powerful combinatorial object that allows to efficiently deal with insertions and deletions in various communication problems:

   • We give a deterministic, linear time synchronization string construction, improving over an \(O(n^5)\) time randomized construction. Independently of this work, a deterministic \(O(n \log^2 \log n)\) time construction proposed by Cheng, Li, and Wu.
   • We give a deterministic construction of an infinite synchronization string which outputs the first \(n\) symbols in \(O(n)\) time. Previously it was not known whether such a string was computable.
   • Both synchronization string constructions are highly explicit, i.e., the \(i\)th symbol can be deterministically computed in \(O(\log i)\) time.
   • This paper also introduces a generalized notion we call long-distance synchronization strings. Such strings allow for local and very fast decoding. In particular, only \(O(\log^3 n)\) time and access to logarithmically many symbols is required to decode any index.

   The paper also provides several applications for these improved synchronization strings:

   • For any \(δ< 1\) and \(ε> 0\) we provide an insdel error correcting block code with rate \(1 - δ- ε\) which can correct any \(O(δ)\) fraction of insertion and deletion errors in \(O(n \log^3 n)\) time. This near linear computational efficiency is surprising given that we do not even know how to compute the (edit) distance between the decoding input and output in sub-quadratic time.
   • We show that local decodability implies that error correcting codes constructed with long-distance synchronization strings can not only efficiently recover from \(δ\) fraction of insdel errors but, similar to [Schulman, Zuckerman; TransInf’99], also from any \(O(δ/ \log n)\) fraction of block transpositions and block replications. These block corruptions allow arbitrarily long substrings to be swapped or replicated anywhere.
   • We show that highly explicitness and local decoding allow for infinite channel simulations with exponentially smaller memory and decoding time requirements. These simulations can then be used to give the first near linear time interactive coding scheme for insdel errors, similar to the result of [Brakerski, Naor; SODA’13] for Hamming errors.

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

   Abstract arXiv BibTex

   @inproceedings{haeupler2017synchronization2,
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad and Vitercik, Ellen},
     title = {Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions},
     booktitle = {Proceedings of the International Conference on Automata, Languages, and Programming (ICALP)},
     pages = {75:1--75:14},
     year = {2018},
     abbr = {ICALP},
     arxiv = {1707.04233}
   }
   

   We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly generalize the usual symbol corruption errors and are much harder to protect against.
   We show how to hide the complications of synchronization errors in many applications by introducing very general channel simulations which efficiently transform an insertion-deletion channel into a regular symbol corruption channel with an error rate larger by a constant factor and a slightly smaller alphabet. We generalize synchronization string based methods which were recently introduced as a tool to design essentially optimal error correcting codes for insertion-deletion channels. Our channel simulations depend on the fact that, at the cost of increasing the error rate by a constant factor, synchronization strings can be decoded in a streaming manner that preserves linearity of time. We also provide a lower bound showing that this constant factor cannot be improved to \(1+ε\), in contrast to what is achievable for error correcting codes. Our channel simulations drastically generalize the applicability of synchronization strings.
   We provide new interactive coding schemes which simulate any interactive two-party protocol over an insertion-deletion channel. Our results improve over the interactive coding scheme of Braverman et al. which achieves a small constant rate and requires exponential time computations. We provide the first computationally efficient interactive coding schemes for synchronization errors, the first coding scheme with a rate approaching one for small noise rates, and also improve over the maximal tolerable error rate. We also show tight connections between synchronization strings and edit-distance tree codes which allow us to transfer results from tree codes directly to edit-distance tree codes.

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

   Abstract arXiv BibTex

   @inproceedings{haeupler2017synchronization,
     title = {Synchronization Strings: Codes for Insertions and Deletions Approaching the {Singleton} Bound},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     booktitle = {Proceedings of the ACM Symposium on Theory of Computing (STOC)},
     pages = {33--46},
     year = {2017},
     abbr = {STOC},
     arxiv = {1704.00807},
     notes = {Invited to be published in the Theory of Computing journal}
   }
   

   We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every \(ε>0\), synchronization strings allow to index a sequence with an \(ε\)^\(-O(1)\) size alphabet such that one can efficiently transform \(k\)  synchronization errors into \((1+ε)k\) half-errors. This powerful new technique has many applications. In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for insertion deletion channels.
   While ECCs for both half-errors and synchronization errors have been intensely studied, the later has largely resisted progress. Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed by Schulman and Zuckerman. Insdel codes for asymptotically large or small noise rates were given in 2016 by Guruswami et al. but these codes are still polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago.
   A direct application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with a slightly larger alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs over large constant alphabets into the realm of insdel codes. Most notably, we obtain efficient insdel codes which get arbitrarily close to the optimal rate-distance tradeoff given by the Singleton bound for the complete noise spectrum.

2014

1. ISIT

   Critical Graphs in Index Coding

   Tahmasbi, M., Shahrasbi, A., and Gohari, A.

   In IEEE International Symposium on Information Theory (ISIT) 2014

   Abstract arXiv BibTex

   @inproceedings{tahmasbi2014critical,
     title = {Critical Graphs in Index Coding},
     author = {Tahmasbi, Mehrdad and Shahrasbi, Amirbehshad and Gohari, Amin},
     booktitle = {IEEE International Symposium on Information Theory (ISIT)},
     pages = {281--285},
     year = {2014},
     organization = {IEEE},
     abbr = {ISIT},
     arxiv = {1312.0132}
   }
   

   In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. Next, we identify a few graph structures that are critical. We also generalize some of our results to the groupcast problem. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.

2021

1. JACM

   Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound

   Haeupler, B., and Shahrasbi, A.

   Journal of the ACM (JACM) 2021

   Abstract arXiv BibTex

   @article{haeupler2017synchronization,
     title = {Synchronization Strings: Codes for Insertions and Deletions Approaching the {Singleton} Bound},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     journal = {Journal of the ACM (JACM)},
     volume = {68},
     number = {5},
     pages = {1--39},
     year = {2021},
     abbr = {JACM},
     arxiv = {1704.00807}
   }
   

   We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every \(ε>0\), synchronization strings allow to index a sequence with an \(ε\)^\(-O(1)\) size alphabet such that one can efficiently transform \(k\)  synchronization errors into \((1+ε)k\) half-errors. This powerful new technique has many applications. In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for insertion deletion channels.
   While ECCs for both half-errors and synchronization errors have been intensely studied, the later has largely resisted progress. Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed by Schulman and Zuckerman. Insdel codes for asymptotically large or small noise rates were given in 2016 by Guruswami et al. but these codes are still polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago.
   A direct application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with a slightly larger alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs over large constant alphabets into the realm of insdel codes. Most notably, we obtain efficient insdel codes which get arbitrarily close to the optimal rate-distance tradeoff given by the Singleton bound for the complete noise spectrum.

2. IEEE Trans.
   Inf. Theory

   Optimally Resilient Codes for List-Decoding from Insertions and Deletions

   Guruswami, V., Haeupler, B., and Shahrasbi, A.

   IEEE Transactions of Information Theory, 2021

   Abstract arXiv BibTex

   @article{guruswami2019optimally,
     author = {Guruswami, Venkatesan and Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     title = {Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
     journal = {IEEE Transactions of Information Theory,},
     year = {2021},
     abbr = {IEEE Trans. 
   Inf. Theory},
     volume = {67},
     number = {12},
     pages = {7837--7856},
     arxiv = {1909.10683}
   }
   

   We give a complete answer to the following basic question: "What is the maximal fraction of deletions or insertions tolerable by q-ary list-decodable codes with non-vanishing information rate?"
   This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results was that a \(γ≤0.707\) fraction of insertions is tolerable by some binary code family.
   For any desired \(\varepsilon>0\), we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of \(γ\) fraction of insertions and \(δ\) fraction of deletions as long as \(γ+2δ≤1-\varepsilon\). On the other hand, for any \(γ, δ\) with \(γ+2δ=1\) list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions.
   We further generalize our result to codes over any finite alphabet of size \(q\). Surprisingly, our work reveals that the feasibility region for \(q>2\) is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a \((q-1\))-piece-wise linear boundary whose \(q\) corner-points lie on a quadratic curve.
   The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of \(δ, γ\) within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAM J. Discrete Math; 2014]. Finally we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate.

3. 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

   Abstract arXiv BibTex

   @article{Review Paper,
     title = {Synchronization Strings and Codes for Insertions and Deletions -- a Survey},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     journal = {IEEE Transactions of Information Theory,},
     year = {2021},
     abbr = {IEEE Trans. 
   Inf. Theory},
     notes = {Invited to IEEE Transactions on Information Theory: Special Issue Dedicated to the Memory of Vladimir I. Levenshtein},
     arxiv = {2101.00711}
   }
   

   Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite significant efforts, progress on designing such codes has been lagging until recently, particularly compared to the detailed understanding of error-correcting codes for symbol substitution or erasure errors. This paper surveys the recent progress in designing efficient error-correcting codes over finite alphabets that can correct a constant fraction of worst-case insertions and deletions.
   Most state-of-the-art results for such codes rely on synchronization strings, simple yet powerful pseudo-random objects that have proven to be very effective solutions for coping with synchronization errors in various settings. This survey also includes an overview of what is known about synchronization strings and discusses communication settings related to error-correcting codes in which synchronization strings have been applied.

4. JACM

   Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound

   Haeupler, B., and Shahrasbi, A.

   Journal of the ACM, 2021

   Abstract arXiv BibTex

   @article{haeupler2017synchronizatioo,
     title = {Synchronization Strings: Codes for Insertions and Deletions Approaching the {Singleton} Bound},
     author = {Haeupler, Bernhard and Shahrasbi, Amirbehshad},
     journal = {Journal of the ACM,},
     year = {2021},
     abbr = {JACM},
     arxiv = {1704.00807}
   }
   

   We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every \(ε>0\), synchronization strings allow to index a sequence with an \(ε\)^\(-O(1)\) size alphabet such that one can efficiently transform \(k\)  synchronization errors into \((1+ε)k\) half-errors. This powerful new technique has many applications. In this paper, we focus on designing insdel codes, i.e., error correcting block codes (ECCs) for insertion deletion channels.
   While ECCs for both half-errors and synchronization errors have been intensely studied, the later has largely resisted progress. Indeed, it took until 1999 for the first insdel codes with constant rate, constant distance, and constant alphabet size to be constructed by Schulman and Zuckerman. Insdel codes for asymptotically large or small noise rates were given in 2016 by Guruswami et al. but these codes are still polynomially far from the optimal rate-distance tradeoff. This makes the understanding of insdel codes up to this work equivalent to what was known for regular ECCs after Forney introduced concatenated codes in his doctoral thesis 50 years ago.
   A direct application of our synchronization strings based indexing method gives a simple black-box construction which transforms any ECC into an equally efficient insdel code with a slightly larger alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs over large constant alphabets into the realm of insdel codes. Most notably, we obtain efficient insdel codes which get arbitrarily close to the optimal rate-distance tradeoff given by the Singleton bound for the complete noise spectrum.

2014

1. JSAC

   Critical graphs in Index Coding

   Tahmasbi, M., Shahrasbi, A., and Gohari, A.

   IEEE Journal on Selected areas in Communications, 2014

   Abstract arXiv BibTex

   @article{tahmasbi2014criticalJournal,
     title = {Critical graphs in Index Coding},
     author = {Tahmasbi, M. and Shahrasbi, A. and Gohari, A.},
     journal = {IEEE Journal on Selected areas in Communications,},
     volume = {33},
     number = {2},
     pages = {225--235},
     year = {2014},
     abbr = {JSAC},
     arxiv = {1312.0132}
   }
   

   In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. Next, we identify a few graph structures that are critical. We also generalize some of our results to the groupcast problem. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.

2020

1. Ph.D. Thesis

   Coding for Synchronization Errors

   Shahrasbi, A.

   2020

   Abstract PDF BibTex

   @phdthesis{ShahrasbiThesis,
     title = {Coding for Synchronization Errors},
     author = {Shahrasbi, Amirbehshad},
     year = {2020},
     school = {Carnegie Mellon University},
     abbr = {Ph.D. Thesis},
     pdf = {Coding for Synchronization Errors.pdf}
   }
   

   Coding theory is the study of algorithms and techniques that facilitate reliable information transmission over noisy mediums, most notably through combinatorial objects called error-correcting codes. Following the inspiring works of Shannon and Hamming, a sophisticated and extensive body of research on error-correcting codes has led to a deep and detailed theoretical understanding as well as practical implementations that have helped fuel the digital revolution. Error-correcting codes can be found in essentially all modern communication, computation, and data storage systems. While being remarkably successful in understanding the theoretical limits and trade-offs of reliable communication under errors and erasures, the coding theory literature significantly lags behind when it comes to overcoming errors that concern the timing of communications. In particular, the study of correcting synchronization errors, i.e., symbol insertions and deletions, while initially introduced by Levenshtein in the 60s, has significantly fallen behind our highly sophisticated knowledge of codes for Hamming-type errors.
   This thesis investigates coding against synchronization errors under a variety of models and attempts to understand trade-offs between different qualities of interest in respective coding schemes such as rate, distance, and algorithmic qualities of the code. Most of the presented results rely on synchronization strings, simple yet powerful pseudorandom objects introduced in this work that have proven to be very effective solutions for coping with synchronization errors in various settings.
   Through indexing with strings that satisfy certain pseudo-random properties, we provide synchronization codes that achieve near-optimal rate-distance trade-off. We further attempt to provide constructions that enable fast encoding/decoding procedures. We study the same problem under the list-decoding regime, where the decoder is expected to provide a short list of codewords that is guaranteed to contain the sent message. We will also try to better understand the fundamental limits of list-decoding for synchronization errors such as the list-decoding capacity or maximal error resilience for list-decodable synchronization codes. This thesis furthermore studies synchronization strings and other related pseudo-random string properties as combinatorial objects that are of independent interest. Such combinatorial objects will be used to extend some of our techniques to alternative communication problems such as coding from block transposition errors or coding for interactive communication.