5 papers
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…
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…
Near-Linear Time Insertion-Deletion Codes and (1+)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
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 i…
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…