Imagen de Portada

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Amir, Amihood, Butman, Ayelet, Itzhaki, Michael, Sokol, Dina
Formato:	Preprint
Publicado:	2026
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

Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
por: Amir, Amihood, et al.
Publicado: (2024)

Combinatorics of Palindromes
por: Itzhaki, Michael
Publicado: (2025)

Asymptotically Optimal Representation of Palindromic Structure
por: Itzhaki, Michael
Publicado: (2024)

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)

Maximal Palindromes in MPC: Simple and Optimal
por: Pissis, Solon P.
Publicado: (2025)

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

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
por: Bathie, Gabriel, et al.
Publicado: (2024)

Longest Common Extensions with Wildcards: Trade-off and Applications
por: Bathie, Gabriel, et al.
Publicado: (2024)

Faster ED-String Matching with $k$ Mismatches
por: Gawrychowski, Paweł, et al.
Publicado: (2025)

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

Online Computation of Palindromes and Suffix Trees on Tries
por: Shibata, Hiroki, et al.
Publicado: (2026)

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

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
por: Chatziafratis, Vaggos, et al.
Publicado: (2023)

Improved Time-Space Tradeoffs for 3SUM-Indexing
por: Dinur, Itai, et al.
Publicado: (2025)

Double-Ended Palindromic Trees in Linear Time
por: Wang, Qisheng, et al.
Publicado: (2022)

Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
por: Habib, Ruhan, et al.
Publicado: (2025)

Optimal $k$-Secretary with Logarithmic Memory
por: Qiao, Mingda, et al.
Publicado: (2025)

Faster Combinatorial k-Clique Algorithms
por: Abboud, Amir, et al.
Publicado: (2024)

Algorithms for Parameterized String Matching with Mismatches
por: Saha, Apurba, et al.
Publicado: (2024)

Time-Optimal $k$-Server
por: Frei, Fabian, et al.
Publicado: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
por: Garg, Sumegha, et al.
Publicado: (2026)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
por: Bernstein, Aaron, et al.
Publicado: (2025)

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
por: Goldenfeld, Michael Elkin Tanya
Publicado: (2026)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
por: Dory, Michal, et al.
Publicado: (2022)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
por: Karczmarz, Adam, et al.
Publicado: (2025)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
por: Woodruff, David P., et al.
Publicado: (2024)

Space-Efficient Text Indexing with Mismatches using Function Inversion
por: Bibbens, Jackson, et al.
Publicado: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
por: Georgiadis, Loukas, et al.
Publicado: (2026)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
por: Zhu, Yanhui, et al.
Publicado: (2024)

Deterministic $k$-Median Clustering in Near-Optimal Time
por: Costa, Martín, et al.
Publicado: (2025)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
por: Draganov, Andrew, et al.
Publicado: (2024)

Time Efficient Implementation for Online $k$-server Problem on Trees
por: Khadiev, Kamil, et al.
Publicado: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
por: Dai, Han, et al.
Publicado: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
por: Nederlof, Jesper
Publicado: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
por: la Tour, Max Dupré, et al.
Publicado: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

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

On $k$-connectivity oracles in $k$-connected graphs
por: Nutov, Zeev
Publicado: (2026)