# Hardness of Frequency-Related Queries on Compressed Strings

Preprint · Rajat De, Dominik Kempa

- Archive id: arxiv:2607.07366
- Published: 2026-07-08
- arXiv: https://arxiv.org/abs/2607.07366
- Source URL: https://arxiv.org/abs/2607.07366
- PDF: https://arxiv.org/pdf/2607.07366
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.