{"ID":6138239,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T12:58:56.760471157Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07366","arxiv_id":"2607.07366","title":"Hardness of Frequency-Related Queries on Compressed Strings","abstract":"Compressed indexing aims to support fundamental string queries in space proportional to compressed input size. For grammar compression, a length-$n$ string $T \\in Σ^n$ represented by a grammar of size $|G|$ can support random access in $O(|G|\\log^{O(1)} n)$ space and $O(\\log^{O(1)} n)$ time, and the same bounds are known for many other queries, including pattern matching, longest common extension, lexicographic predecessor/successor, the Burrows-Wheeler transform, suffix arrays, and suffix trees. Frequency-related queries remain less understood. These include rank queries, which report the number of occurrences of a symbol $c \\in Σ$ in a substring $T(b..e]$, and symbol occurrence queries, which ask whether $c$ occurs in $T(b..e]$. No fully general data structure is known for these queries with $O(|G|\\log^{O(1)} n)$ space and $O(\\log^{O(1)} n)$ query time. We establish new conditional lower bounds for such problems. First, we show that answering rank and symbol occurrence queries on grammar-compressed texts in polylogarithmic time using an $O(|G|\\log^{O(1)} n)$-space structure constructible in $O(|G|\\log^{O(1)} n)$ time would imply an $O(n^2\\log^{O(1)} n)$-time algorithm for Boolean Matrix Multiplication. The proof uses a more general lower bound for efficiently answering a batch of such queries. Second, we extend the exact lower bounds from straight-line programs to LZ78-compressed strings, a weaker compression model. Third, independently, we show that even additive approximations of rank queries on straight-line grammars would imply faster Boolean Matrix Multiplication algorithms. Finally, assuming the Orthogonal Vectors conjecture, we show that other frequency-related problems, including range distinct counting and range mode frequency, also cannot be efficiently supported in compressed space.","short_abstract":"Compressed indexing aims to support fundamental string queries in space proportional to compressed input size. For grammar compression, a length-$n$ string $T \\in Σ^n$ represented by a grammar of size $|G|$ can support random access in $O(|G|\\log^{O(1)} n)$ space and $O(\\log^{O(1)} n)$ time, and the same bounds are kno...","url_abs":"https://arxiv.org/abs/2607.07366","url_pdf":"https://arxiv.org/pdf/2607.07366v1","authors":"[\"Rajat De\",\"Dominik Kempa\"]","published":"2026-07-08T13:01:18Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}