Tight Lower Bounds for Central String Queries in Compressed Space

In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text \(T \in \Sigma^n\) while using space proportional to the size of \(T\) in compressed form. Nearly all fundamental queries can currently be efficiently supported in \(\mathcal{O}(\delta(T)\log^{\mathcal{O}(1)} n)\) space, where \(\delta(T)\) is the substring complexity—a strong compressibility measure that lower-bounds the optimal space required to represent the text [Kociumaka, Navarro, Prezza; IEEE Trans. Inf. Theory 2023]. In contrast, the optimal query time for compressed data structures has been characterized only for the basic random access problem.