Imagen de Portada

Near-Optimal Property Testers for Pattern Matching

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Jin, Ce, Kociumaka, Tomasz
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

Approximate Circular Pattern Matching
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2022)

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

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

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

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
por: Boneh, Itai, et al.
Publicado: (2025)

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

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

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

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

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

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

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

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

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
por: Fischer, Nick, et al.
Publicado: (2024)

0-1 Knapsack in Nearly Quadratic Time
por: Jin, Ce
Publicado: (2023)

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

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

Nearly Optimal Internal Dictionary Matching
por: Chen, Jingbang, et al.
Publicado: (2023)

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

A Tolerant Independent Set Tester
por: Seth, Cameron
Publicado: (2025)

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

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Memory Reallocation with Polylogarithmic Overhead
por: Jin, Ce
Publicado: (2026)

Faster Algorithms for Text-to-Pattern Hamming Distances
por: Chan, Timothy M., et al.
Publicado: (2023)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
por: Casel, Katrin, et al.
Publicado: (2019)

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

On the Structure of Replicable Hypothesis Testers
por: Aamand, Anders, et al.
Publicado: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
por: Feng, Weiming, et al.
Publicado: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
por: Jin, Ce, et al.
Publicado: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
por: Jin, Ce, et al.
Publicado: (2024)

Quantum Pattern Matching with Wildcards
por: Seddighin, Masoud, et al.
Publicado: (2025)

Pattern Matching with Mismatches and Wildcards
por: Bathie, Gabriel, et al.
Publicado: (2024)

Dynamic Pattern Matching with Wildcards
por: Naeini, Arshia Ataee, et al.
Publicado: (2026)

Enhanced Graph Pattern Matching
por: Cotumaccio, Nicola
Publicado: (2024)