Tight Lower Bounds for Central String Queries in Compressed Space

In this work, we study limits of compressed data structures, i.e., data structures that support various queries on the input text T ∈ Σ n in space proportional to the size of T in compressed form. On the upper bound side, currently nearly all fundamental queries can be efficiently supported in O(δ(T ) log O(1) n) space (where δ(T ) is the substring complexity -a strong measure of compressibility that lower-bounds the optimal achievable space to represent the text [Kociumaka, Navarro, Prezza, IEEE Trans. Inf. Theory 2023]); this includes queries like random access, longest common extension, suffix array, longest common prefix array, and many others. In contrast, lower bounds for compressed data structures remained elusive, and currently they are known only for the basic random access problem. This work addresses this important gap and develops tight lower bounds for nearly all other fundamental queries: