@inproceedings{AndoniKrauthgamerOnak2010,
  author = {Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak},
  title = {Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity},
  booktitle = {2010 IEEE 51st Annual Symposium on Foundations of Computer Science},
  publisher = {IEEE Computer Society},
  year = {2010},
  pages = {377--386},
  doi = {10.1109/FOCS.2010.43},
  eprint = {1005.4033},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  url = {https://arxiv.org/abs/1005.4033v1},
  note = {Theorem numbers refer to the full version, arXiv:1005.4033v1}
}

@inproceedings{AndoniKrauthgamerOnak2011,
  author = {Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak},
  title = {Streaming Algorithms via Precision Sampling},
  booktitle = {2011 IEEE 52nd Annual Symposium on Foundations of Computer Science},
  publisher = {IEEE Computer Society},
  year = {2011},
  pages = {363--372},
  doi = {10.1109/FOCS.2011.82},
  eprint = {1011.1263},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  url = {https://arxiv.org/abs/1011.1263v2},
  note = {Full version titled ``Streaming Algorithms from Precision Sampling''; Lemma 1.2 in arXiv:1011.1263v2}
}

@inproceedings{AndoniNosatzki2020,
  author = {Andoni, Alexandr and Nosatzki, Negev Shekel},
  title = {Edit Distance in Near-Linear Time: It's a Constant Factor},
  booktitle = {Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science},
  pages = {990--1001}, year = {2020}, doi = {10.1109/FOCS46700.2020.00096},
  note = {Full version: arXiv:2005.07678v2, 2022}
}

@article{AndoniOnak2012,
  author = {Andoni, Alexandr and Onak, Krzysztof},
  title = {Approximating Edit Distance in Near-Linear Time}, journal = {SIAM Journal on Computing},
  volume = {41}, number = {6}, pages = {1635--1648}, year = {2012},
  doi = {10.1137/090767182},
  note = {Preliminary version in STOC 2009, pages 199--204}
}

@article{BackursIndyk2018,
  author = {Backurs, Arturs and Indyk, Piotr},
  title = {Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless {SETH} Is False)},
  journal = {SIAM Journal on Computing}, volume = {47}, number = {3},
  pages = {1087--1097}, year = {2018}, doi = {10.1137/15M1053128}
}

@inproceedings{BarYossefEtAl2004,
  author = {Bar-Yossef, Ziv and Jayram, T. S. and Krauthgamer, Robert and Kumar, Ravi},
  title = {Approximating Edit Distance Efficiently},
  booktitle = {Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science},
  pages = {550--559}, year = {2004}, doi = {10.1109/FOCS.2004.14}
}

@inproceedings{BatuErgunSahinalp2006,
  author = {Batu, Tu{\u g}kan and Erg{\"u}n, Funda and Sahinalp, Cenk},
  title = {Oblivious String Embeddings and Edit Distance Approximations},
  booktitle = {Proceedings of the 17th Annual ACM--SIAM Symposium on Discrete Algorithms},
  pages = {792--801}, year = {2006}, doi = {10.1145/1109557.1109644}
}

@inproceedings{BatuEtAl2003,
  author = {Batu, Tu{\u g}kan and Erg{\"u}n, Funda and Kilian, Joe and Magen, Avner
    and Raskhodnikova, Sofya and Rubinfeld, Ronitt and Sami, Rahul},
  title = {A Sublinear Algorithm for Weakly Approximating Edit Distance},
  booktitle = {Proceedings of the 35th Annual ACM Symposium on Theory of Computing},
  pages = {316--324}, year = {2003}, doi = {10.1145/780542.780590}
}

@inproceedings{BrakensiekRubinstein2020,
  author = {Brakensiek, Joshua and Rubinstein, Aviad},
  title = {Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time},
  booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {685--698}, year = {2020}, doi = {10.1145/3357713.3384282}
}

@misc{BringmannCassisFischerKociumaka2023,
  author = {Karl Bringmann and Alejandro Cassis and Nick Fischer and Tomasz Kociumaka},
  title = {Faster Sublinear-Time Edit Distance},
  year = {2023}, eprint = {2312.01759}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 1, December 4, 2023},
  url = {https://arxiv.org/abs/2312.01759v1}
}

@article{ChakrabortyEtAl2020,
  author = {Chakraborty, Diptarka and Das, Debarati and Goldenberg, Elazar
    and Kouck{\'y}, Michal and Saks, Michael},
  title = {Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time},
  journal = {Journal of the ACM}, volume = {67}, number = {6},
  pages = {36:1--36:22}, year = {2020}, doi = {10.1145/3422823}
}

@misc{DasKipouridisKociumaka2026,
  author = {Debarati Das and Evangelos Kipouridis and Tomasz Kociumaka},
  title = {Metric Weighted Edit Distance: A $(3+\varepsilon)$-Approximation in $\widetilde{O}_{\varepsilon}(N^{1.6})$ Time},
  year = {2026}, eprint = {2609.20796}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 1, September 17, 2026},
  url = {https://arxiv.org/abs/2609.20796v1}
}

@article{FrankWolfe1956,
  author = {Marguerite Frank and Philip Wolfe},
  title = {An Algorithm for Quadratic Programming},
  journal = {Naval Research Logistics Quarterly},
  volume = {3},
  number = {1--2},
  pages = {95--110},
  year = {1956},
  doi = {10.1002/nav.3800030109},
  url = {https://doi.org/10.1002/nav.3800030109}
}

@article{FreundSchapire1997,
  author = {Yoav Freund and Robert E. Schapire},
  title = {A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting},
  journal = {Journal of Computer and System Sciences},
  volume = {55},
  number = {1},
  pages = {119--139},
  year = {1997},
  doi = {10.1006/jcss.1997.1504},
  url = {https://doi.org/10.1006/jcss.1997.1504}
}

@misc{GoldenbergRubinsteinSaha2021,
  author = {Elazar Goldenberg and Aviad Rubinstein and Barna Saha},
  title = {Does Preprocessing Help in Fast Sequence Comparisons?},
  year = {2021}, eprint = {2108.09115}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 1, August 20, 2021; conference version STOC 2020},
  url = {https://arxiv.org/abs/2108.09115v1}
}

@misc{HaeuplerRubinsteinShahrasbi2019,
  author = {Bernhard Haeupler and Aviad Rubinstein and Amirbehshad Shahrasbi},
  title = {Near-Linear Time Insertion-Deletion Codes and $(1+\varepsilon)$-Approximating Edit Distance via Indexing},
  year = {2019}, eprint = {1810.11863}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 2, April 9, 2019},
  url = {https://arxiv.org/abs/1810.11863v2}
}

@inproceedings{IndykWoodruff2005,
  author = {Piotr Indyk and David Woodruff},
  title = {Optimal Approximations of the Frequency Moments of Data Streams},
  booktitle = {Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing},
  publisher = {Association for Computing Machinery},
  year = {2005},
  url = {https://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/iw05.pdf}
}

@inproceedings{Jaggi2013,
  author = {Martin Jaggi},
  title = {Revisiting {Frank--Wolfe}: Projection-Free Sparse Convex Optimization},
  booktitle = {Proceedings of the 30th International Conference on Machine Learning},
  series = {Proceedings of Machine Learning Research},
  volume = {28},
  pages = {427--435},
  year = {2013},
  publisher = {PMLR},
  url = {https://proceedings.mlr.press/v28/jaggi13.html}
}

@inproceedings{KouckySaks2020,
  author = {Kouck{\'y}, Michal and Saks, Michael},
  title = {Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time},
  booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {699--712}, year = {2020}, doi = {10.1145/3357713.3384307}
}

@misc{KouckySaks2024,
  author = {Michal Kouck\'y and Michael Saks},
  title = {Almost Linear Size Edit Distance Sketch},
  year = {2024}, eprint = {2406.11225}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 1, June 17, 2024},
  url = {https://arxiv.org/abs/2406.11225v1}
}

@article{LandauVishkin1988,
  author = {Landau, Gad M. and Vishkin, Uzi}, title = {Fast String Matching with {$k$} Differences},
  journal = {Journal of Computer and System Sciences}, volume = {37}, number = {1},
  pages = {63--78}, year = {1988}, doi = {10.1016/0022-0000(88)90045-1}
}

@article{LandauVishkin1989,
  author = {Landau, Gad M. and Vishkin, Uzi},
  title = {Fast Parallel and Serial Approximate String Matching},
  journal = {Journal of Algorithms}, volume = {10}, number = {2}, pages = {157--169},
  year = {1989}, doi = {10.1016/0196-6774(89)90010-2}
}

@article{Levenshtein1966,
  author = {Levenshtein, Vladimir I.},
  title = {Binary Codes Capable of Correcting Deletions, Insertions, and Reversals},
  journal = {Soviet Physics Doklady}, volume = {10}, number = {8},
  pages = {707--710}, year = {1966},
  note = {English translation of Doklady Akademii Nauk SSSR 163(4), 845--848 (1965)}
}

@misc{MaderTavasoliWang2026,
  author = {Ethan Mader and Borna Tavasoli and Jihan Wang},
  title = {A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics},
  year = {2026}, eprint = {2609.14873}, archivePrefix = {arXiv},
  primaryClass = {cs.DS}, note = {Version 1, September 14, 2026},
  url = {https://arxiv.org/abs/2609.14873v1}
}

@inproceedings{MaoRubinstein2026,
  author = {Xiao Mao and Aviad Rubinstein},
  title = {Approximation Schemes for Edit Distance and {LCS} in Quasi-Strongly Subquadratic Time},
  booktitle = {Proceedings of the 58th Annual ACM Symposium on Theory of Computing},
  publisher = {Association for Computing Machinery},
  year = {2026},
  doi = {10.1145/3798129.3800789},
  eprint = {2603.29702},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  url = {https://arxiv.org/abs/2603.29702v1},
  note = {Theorem numbers refer to the full version, arXiv:2603.29702v1}
}

@article{MasekPaterson1980,
  author = {Masek, William J. and Paterson, Michael S.},
  title = {A Faster Algorithm Computing String Edit Distances},
  journal = {Journal of Computer and System Sciences}, volume = {20}, number = {1},
  pages = {18--31}, year = {1980}, doi = {10.1016/0022-0000(80)90002-1}
}

@article{Myers1986,
  author = {Myers, Eugene W.}, title = {An {$O(ND)$} Difference Algorithm and Its Variations},
  journal = {Algorithmica}, volume = {1}, pages = {251--266}, year = {1986},
  doi = {10.1007/BF01840446}
}

@misc{OpenAIEditDistortion2026,
  author = {{OpenAI}},
  title = {{Edit Distance in $\ell_1$: Matching Bounds up to Constants in the Exponent}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026/paper.pdf}{OAI:Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026}},
  year = {2026}
}

@article{OstrovskyRabani2007,
  author = {Ostrovsky, Rafail and Rabani, Yuval},
  title = {Low Distortion Embeddings for Edit Distance}, journal = {Journal of the ACM},
  volume = {54}, number = {5}, pages = {23:1--23:16}, year = {2007},
  doi = {10.1145/1284320.1284322}
}

@inproceedings{RakhlinSridharan2013,
  author = {Alexander Rakhlin and Karthik Sridharan},
  title = {Online Learning with Predictable Sequences},
  booktitle = {Proceedings of the 26th Annual Conference on Learning Theory},
  series = {Proceedings of Machine Learning Research},
  volume = {30},
  pages = {993--1019},
  year = {2013},
  publisher = {PMLR},
  url = {https://proceedings.mlr.press/v30/Rakhlin13.html}
}

@techreport{Tropp2021Probability,
  author = {Joel A. Tropp},
  title = {{ACM 217}: Probability in High Dimensions},
  institution = {California Institute of Technology},
  type = {Caltech CMS Lecture Notes},
  number = {2021-01},
  address = {Pasadena},
  year = {2021},
  month = mar,
  note = {Corrected March 2023; Theorem 4.16},
  doi = {10.7907/mxr0-c422},
  url = {https://tropp.caltech.edu/notes/Tro21-Probability-High-LN-corr.pdf}
}

@article{Ukkonen1985,
  author = {Ukkonen, Esko}, title = {Algorithms for Approximate String Matching},
  journal = {Information and Control}, volume = {64}, number = {1--3},
  pages = {100--118}, year = {1985}, doi = {10.1016/S0019-9958(85)80046-2}
}

@article{WagnerFischer1974,
  author = {Wagner, Robert A. and Fischer, Michael J.},
  title = {The String-to-String Correction Problem}, journal = {Journal of the ACM},
  volume = {21}, number = {1}, pages = {168--173}, year = {1974},
  doi = {10.1145/321796.321811}
}