Kociumaka, Tomasz

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes

2026 · Open MIND

A Random Access query to a string $T\in [0..σ)^n$ asks for the character $T[i]$ at a given position $i\in [0..n)$. In $O(n\logσ)$ bits of space, this fundamental task admits constant-time queries. While this is optimal …