Fetching the paper…
Reading the bibliography…
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 result was that a $\gamma\leq 0.707$ fraction of insertions is tolerable by some binary code family.
Binary codes capable of correcting deletions, insertions, and reversals
Vladimir Levenshtein · 1965
Earlier work this paper cites.
Expected length of longest common subsequences
Vladimír Dančík · 1994
Earlier work this paper cites.
Upper bounds for the expected length of a longest common subsequence of two binary sequences
Vlado Dančík and Mike Paterson · 1995
Earlier work this paper cites.
Asymptotically good codes correcting insertions, deletions, and transpositions
Leonard J. Schulman and David Zuckerman · 1999
Earlier work this paper cites.
On single-deletion-correcting codes
Neil J. A Sloane · 2002
Earlier work this paper cites.
Expected length of the longest common subsequence for large alphabets
Marcos Kiwi, Martin Loebl, and Jiří Matoušek · 2005
Earlier work this paper cites.
Channel polarization: A method for constructing capacity-achieving codes
Erdal Arikan · 2008
Earlier work this paper cites.
Improved bounds on the average length of longest common subsequences
George S Lueker · 2009
Earlier work this paper cites.
A survey of results for deletion channels and related synchronization channels
Michael Mitzenmacher · 2009
Earlier work this paper cites.
A survey of error-correcting codes for channels with symbol synchronization errors
Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh · 2010
Earlier work this paper cites.
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound
Venkatesan Guruswami and Chaoping Xing · 2013
Earlier work this paper cites.
Longest common subsequences in sets of words
Boris Bukh and Jie Ma · 2014
Cited alongside, same era.
An improved bound on the fraction of correctable deletions
Boris Bukh and Venkatesan Guruswami · 2016
Cited alongside, same era.
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes
Venkatesan Guruswami and Ray Li · 2016
Cited alongside, same era.
An improved bound on the fraction of correctable deletions
Boris Bukh, Venkatesan Guruswami, and Johan Håstad · 2017
Cited alongside, same era.
Deletion codes in the high-noise and high-rate regimes
Venkatesan Guruswami and Carol Wang · 2017
Cited alongside, same era.
Synchronization strings: Codes for insertions and deletions approaching the singleton bound
Bernhard Haeupler and Amirbehshad Shahrasbi · 2017
Cited alongside, same era.
Synchronization strings: List decoding for insertions and deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, and Madhu Sudan · 2018
Later among the works it cites.
Synchronization strings: Channel simulations and interactive coding for insertions and deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik · 2018
Later among the works it cites.
On the list decodability of insertions and deletions
Tomohiro Hayashi and Kenji Yasunaga · 2018
Later among the works it cites.
List decoding of insertions and deletions
Antonia Wachter-Zeh · 2018
Later among the works it cites.
Synchronization strings: highly efficient deterministic constructions over small alphabets
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, and Ke Wu · 2019
Closest in time.
Block edit errors with transpositions: Deterministic document exchange protocols and almost optimal binary codes
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
General strong polarization
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan · 2018
Cited alongside, same era.
Efficient low-redundancy codes for correcting multiple deletions
Joshua Brakensiek, Venkatesan Guruswami, and Samuel Zbarsky · 2018
Cited alongside, same era.
Deterministic document exchange protocols, and almost optimal binary codes for edit errors
Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu · 2018
Cited alongside, same era.
Coding against deletions in oblivious and online models
Venkatesan Guruswami and Ray Li · 2018
Cited alongside, same era.
Synchronization strings: Explicit constructions, local decoding, and applications
Bernhard Haeupler and Amirbehshad Shahrasbi · 2018
Cited alongside, same era.
Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu · 2019
Closest in time.
Optimal document exchange and new codes for insertions and deletions
Bernhard Haeupler · 2019
Closest in time.
Near-linear time insertion-deletion codes and (1+ ε \varepsilon )-approximating edit distance via indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi · 2019
Closest in time.
Shu Liu, Ivan Tjuawinata, and Chaoping Xing · 2019
Closest in time.
List decoding of insertion and deletion codes
Shu Liu, Ivan Tjuawinata, and Chaoping Xing · 2019
Closest in time.