Related references
Note: Only part of the references are listed.Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg et al.
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20) (2020)
Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time For
Joshua Brakensiek et al.
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20) (2020)
Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time
Michal Koucky et al.
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20) (2020)
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
Bernhard Haeupler et al.
PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19) (2019)
Improved MPC Algorithms for Edit Distance and Ulam Distance
Mahdi Boroujeni et al.
SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019 (2019)
Round Compression for Parallel Matching Algorithms
Artur Czumaj et al.
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2018)
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Diptarka Chakraborty et al.
2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) (2018)
Efficient Massively Parallel Methods for Dynamic Programming
Sungjin Im et al.
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2017)
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs et al.
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING (2015)
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni et al.
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING (2014)