On Hardness of Jumbled Indexing

DOI10.1007/978-3-662-43948-7_10zbMath1398.68698arXiv1405.0189OpenAlexW1814243895MaRDI QIDQ5167735

Amihood Amir, Noa Lewenstein, Timothy M. Chan, Moshe Lewenstein

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.0189

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Weighted prefix normal words: mind the gap ⋮ Permuted scaled matching ⋮ Fast algorithms for abelian periods in words and greatest common divisor queries ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Gapped indexing for consecutive occurrences ⋮ Hardness of RNA folding problem with four symbols ⋮ Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ Unnamed Item ⋮ On infinite prefix normal words ⋮ On Multidimensional and Monotone k-SUM ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Bubble-flip -- a new generation algorithm for prefix normal words ⋮ Unnamed Item