46 citations · 96 across the 8 of their papers we have counts for
8 papers · 1 filter
Synchronization Strings and Codes for Insertions and Deletions -- a Survey
Bernhard Haeupler, Amirbehshad Shahrasbi
Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite s…
Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes
Bernhard Haeupler, Amirbehshad Shahrasbi
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 a…
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
We give a complete answer to the following basic question: "What is the maximal fraction of deletions or insertions tolerable by -ary list-decodable codes with non-vanishing inf…
Synchronization Strings: List Decoding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
We study codes that are list-decodable under insertions and deletions. Specifically, we consider the setting where a codeword over some finite alphabet of size may suffer from…
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler, Amirbehshad Shahrasbi
This paper gives new results for synchronization strings, a powerful combinatorial object that allows to efficiently deal with insertions and deletions in various communication set…
Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik
We present many new results related to reliable (interactive) communication over insertion-deletion channels. Synchronization errors, such as insertions and deletions, strictly gen…
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Bernhard Haeupler, Amirbehshad Shahrasbi
We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more gen…
Critical Graphs in Index Coding
Mehrdad Tahmasbi, Amirbehshad Shahrasbi, Amin Gohari
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…