Does there exist a family of data structures which, for every binary text T∈0,1^n, uses O(n) bits of space and answers suffix-array access queries operatornameSA_T[i] for every i∈1,…,n in O(1) cell probes, in the cell-probe model with word size Theta(log n)? Here operatornameSA_T[i] is the starting position of the i-th suffix of T in lexicographic order.

Grossi–Vitter constant-time suffix-array representation question

Does there exist a family of data structures which, for every binary text $T\in\{0,1\}^n$ , uses $O(n)$ bits of space and answers suffix-array access queries $\operatorname{SA}_T[i]$ for every $i\in\{1,\ldots,n\}$ in $O(1)$ cell probes, in the cell-probe model with word size $\Theta(\log n)$ ? Here $\operatorname{SA}_T[i]$ is the starting position of the $i$ -th suffix of $T$ in lexicographic order.

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries — arXiv

data-structures theoretical-computer-science

1 day ago

Progress summary

Refreshed 1 day ago

Claimed solved

A new preprint claims to rule out constant-time suffix-array access using only linear space on binary texts, but the claim has not yet been independently verified.

The question asks whether suffix-array access can be represented in linear space with constant query time, even for binary texts. A new preprint claims a cell-probe lower bound that rules this out.

August 2026 cell-probe lower bound

The preprint claims a nontrivial time-space lower bound and complexity-preserving reductions to prefix-query problems; its stated consequence is that linear-space, constant-time suffix-array access is impossible for binary texts. Earlier work established bidirectional reductions between suffix-array queries and prefix-select queries, together with subpolynomial-time tradeoffs, but did not establish this impossibility result.

Current status (as of August 2026): A preprint claims the lower bound settles the impossibility direction, while independent verification and peer-reviewed confirmation are not recorded.

Sources

No solutions have been posted yet.