Copertina

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Boneh, Itai, Gorbachev, Egor, Kociumaka, Tomasz
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
di: Gorbachev, Egor, et al.
Pubblicazione: (2024)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2025)

Pattern Matching under Weighted Edit Distance
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
di: Gawrychowski, Paweł, et al.
Pubblicazione: (2024)

Tight Lower Bounds for Central String Queries in Compressed Space
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Hairpin Completion Distance Lower Bound
di: Boneh, Itai, et al.
Pubblicazione: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
di: Das, Debarati, et al.
Pubblicazione: (2025)

The Communication Complexity of Pattern Matching with Edits Revisited
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2026)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2014)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
di: Duyster, Anouk, et al.
Pubblicazione: (2025)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
di: Bathie, Gabriel, et al.
Pubblicazione: (2023)

Near-Optimal Property Testers for Pattern Matching
di: Jin, Ce, et al.
Pubblicazione: (2025)

Hamming Distance Oracle
di: Boneh, Itai, et al.
Pubblicazione: (2024)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
di: Boneh, Itai, et al.
Pubblicazione: (2025)

Dynamic PageRank: Algorithms and Lower Bounds
di: Jayaram, Rajesh, et al.
Pubblicazione: (2024)

Approximate Circular Pattern Matching under Edit Distance
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2024)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
di: Bringmann, Karl, et al.
Pubblicazione: (2024)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
di: Goldenberg, Elazar, et al.
Pubblicazione: (2022)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
di: Boneh, Itai, et al.
Pubblicazione: (2025)

Space-Efficient k-Mismatch Text Indexes
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
di: Kempa, Dominik, et al.
Pubblicazione: (2024)

Time-Optimal Construction of String Synchronizing Sets
di: Ellert, Jonas, et al.
Pubblicazione: (2026)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
di: Kempa, Dominik, et al.
Pubblicazione: (2023)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
di: Duyster, Anouk, et al.
Pubblicazione: (2026)

On the Communication Complexity of Approximate Pattern Matching
di: Kociumaka, Tomasz, et al.
Pubblicazione: (2024)

Searching 2D-Strings for Matching Frames
di: Boneh, Itai, et al.
Pubblicazione: (2023)

Faster Algorithms for Longest Common Substring
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2021)

New Algorithms and Lower Bounds for Streaming Tournaments
di: Ghosh, Prantar, et al.
Pubblicazione: (2024)

Approximate Circular Pattern Matching
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2022)

Lower Bounds for Non-adaptive Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
di: Funke, Daniel, et al.
Pubblicazione: (2024)

Balancing Two-Dimensional Straight-Line Programs
di: Boneh, Itai, et al.
Pubblicazione: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
di: Fleming, Noah, et al.
Pubblicazione: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
di: Nogler, Jakob, et al.
Pubblicazione: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
di: Jin, Billy, et al.
Pubblicazione: (2023)