# On Hardness of Jumbled Indexing

arXiv: https://arxiv.org/abs/1405.0189 · HTML: https://mlsanity.com/paper/1405.0189/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2014.

## Built on by (most cited first, 1 of 1)

- [Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection](https://mlsanity.com/paper/2601.09577/) (2026)

## Abstract (arXiv)

Jumbled indexing is the problem of indexing a text T for queries that ask whether there is a substring of T matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each character. Jumbled indexing has garnered a lot of interest in the last four years. There is a naive algorithm that preprocesses all answers in O(n2|Sigma|) time allowing quick queries afterwards, and there is another naive algorithm that requires no preprocessing but has O(nlog|Sigma|) query time. Despite a tremendous amount of effort there has been little improvement over these running times. In this paper we provide good reason for this. We show that, under a 3SUM-hardness assumption, jumbled indexing for alphabets of size ω(1) requires Omega(n2-ε) preprocessing time or Omega(n1-δ) query time for any ε,δ>0. In fact, under a stronger 3SUM-hardness assumption, for any constant alphabet size r≥ 3 there exist describable fixed constant εr and δr such that jumbled indexing requires Omega(n2-εr) preprocessing time or Omega(n1-δr) query time.