On List Decoding of Insertion and Deletion Errors

V. Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions and Reversals, Doklady Akademii Nauk SSSR,

1965

Earlier work this paper cites.

R. R. Varshamov and G. M. Tenengolts, Codes which Correct Single Asymmetric Errors (in Russian), Automatika i Telemkhanika

1965

Earlier work this paper cites.

V. Levenshtein, Asymptotically Optimum Binary Code with Correction for Losses of One or Two Adjacent Bits, Problemy Kibernetiki,

1967

Earlier work this paper cites.

V. Levenshtein, Elements of Coding Theory (in Russian), Discrete Mathematics and Mathematical Problems of Cybernetics

1980

Earlier work this paper cites.

G. M. Tenengolts, Nonbinary Codes, Correcting Single Deletion or Insertion (Corresp.), IEEE Transactions on Information Theory,

1984

Earlier work this paper cites.

V. Guruswami and M. Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on,

1998

Earlier work this paper cites.

D. S. Hirschberg, Bounds on the Number of String Subsequences, Annual Symposium on Combinatorial Pattern Matching

1999

Earlier work this paper cites.

E. Brill, R. C. Moore, An Improved Error Model for Noisy Channel Spelling Correction, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics (ACL ’00)

2000

Earlier work this paper cites.

V.I. Levenshtein, “Efficient Reconstruction of Sequences from their Subsequences or Supersequences,” Journal of Combinatorial Theory,

2001

Earlier work this paper cites.

F. J. Och, Minimum Error Rate Training in Statistical Machine Translation, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 1 (ACL ’03),Association for Computational Linguistics, Stroudsburg, PA, USA,

2003

Earlier work this paper cites.

R. Xu and D. Wunsch, Survey of Clustering Algorithms, IEEE Transactions on Neural Networks

2005

Earlier work this paper cites.

V. Guruswami and A. Rudra, Explicit Codes Achieving List Decoding Capacity : Error Correction with Optimal Redundancy, IEEE Transactions on Information Theory,

2008

Earlier work this paper cites.

M. Mitzenmacher, Capacity Bounds for Sticky Channels, IEEE Transactions on Information Theory

2008

Earlier work this paper cites.

V. Guruswami and S. Vadhan, A Lower Bound on List Size for List Decoding, IEEE Transactions on Information Theory,

2010

Earlier work this paper cites.

V. Guruswami, Linear-Algebraic List Decoding of Folded Reed-Solomon Codes, Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity (CCC ’11), IEEE Computer Society,

2011

Cited alongside, same era.

V. Guruswami and C. Wang. Optimal Rate List Decoding via Derivative Codes, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques,

2011

Cited alongside, same era.

V. Guruswami and C. Xing, List Decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin Subcodes up to the Singleton Bound, Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing

2013

Cited alongside, same era.

L. Cheng, T. G. Swart, H. C. Ferreira, and K. A. S. Abdel-Ghaffar, Codes for Correcting Three or More Adjacent Deletions or Insertions, IEEE International Symposium of Information Theory (ISIT)

2014

Cited alongside, same era.

S. Jain, F. F. Hassanzadeh, M. Schwartz and J. Bruck, Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms, IEEE Transactions on Information Theory,

2017

Later among the works it cites.

A. Lenz, A. Wachter-Zeh, and E. Yaakobi, Bounds on Codes Correcting Tandem and Palindromic Duplications, Int. Workshop on Coding and Cryptography (WCC)

2017

Later among the works it cites.

C. Schoeny, A. Wachter-Zeh, R. Gabrys and E. Yaakobi, Codes Correcting a Burst of Deletions or Insertions, IEEE Transactions on Information Theory

2017

Later among the works it cites.

J. Brakensiek, V. Guruswami and S. Zbarsky, Efficient Low- Redundancy Codes for Correcting Multiple Deletions, IEEE Transactions on Information Theory,

2018

Later among the works it cites.

B. Haeupler, A. Shahrasbi, M. Sudan, Synchronization Strings: List Decoding for Insertions and Deletions, 45th International Colloquium on Automata, Languages and Programming (ICALP)