Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amir, Amihood, Butman, Ayelet, Itzhaki, Michael, Sokol, Dina
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Combinatorics of Palindromes
by: Itzhaki, Michael
Published: (2025)

Asymptotically Optimal Representation of Palindromic Structure
by: Itzhaki, Michael
Published: (2024)

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

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

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

Quantum Pattern Matching with Wildcards
by: Seddighin, Masoud, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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