Efficiently Approximating Edit Distance Between Pseudorandom Strings

DOI10.1137/1.9781611975482.71zbMath1431.68173arXiv1811.04300OpenAlexW2952972528MaRDI QIDQ5236255

William Kuszmaul

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.04300

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items

Train tracks with gaps: applying the probabilistic method to trains, Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation