Synchronization strings: codes for insertions and deletions approaching the Singleton bound
From MaRDI portal
Abstract: 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 , synchronization strings allow to index a sequence with an size alphabet such that one can efficiently transform synchronization errors into 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.
Recommendations
- Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
- Synchronization strings: list decoding for insertions and deletions
- Synchronization strings: explicit constructions, local decoding, and applications
- Synchronization strings: highly efficient deterministic constructions over small alphabets
- Synchronization strings: channel simulations and interactive coding for insertions and deletions
Cited in
(15)- On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability
- Construction of single quantum deletion codes via combinatorial conditions and adjacency matrices
- Synchronization strings: channel simulations and interactive coding for insertions and deletions
- Synchronization strings: list decoding for insertions and deletions
- Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
- Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing
- Synchronization strings: explicit constructions, local decoding, and applications
- Synchronization strings: highly efficient deterministic constructions over small alphabets
- Information-Theoretic Foundations of DNA Data Storage
- Insdel codes from subspace and rank-metric codes
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- Efficient Linear and Affine Codes for Correcting Insertions/Deletions
- Deterministic document exchange protocols and almost optimal binary codes for edit errors
- New dimension-independent upper bounds on linear insdel codes
- Shortest synchronizing strings for Huffman codes
This page was built for publication: Synchronization strings: codes for insertions and deletions approaching the Singleton bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977959)
