Search Results

Compressed indexing is a recent trend in the design of data structures that aims to support fundamental string queries in space proportional to the size of the data in compressed form. One of the most popular compression frameworks in this field is grammar compression. A length-n string T ∈ Σⁿ (where Σ is any finite set of size up to |Σ| = |T|^𝒪(1)) represented using a context-free grammar of size |G| can be augmented to support random access queries (given any i ∈ [1..n], return T[i]) in 𝒪(|G| log^𝒪(1) n) space and 𝒪(log^𝒪(1) n) time. Numerous other queries, including pattern matching, longest common extension, lexicographical predecessor/successor, Burrows-Wheeler Transform, suffix array, and even suffix tree queries, can also be supported within the same bounds. Despite this progress, one fundamental class of queries has remained elusive: frequency-related queries, such as reporting the number of occurrences of a symbol c ∈ Σ in a substring T(b..e] (the so-called rank query), or simply checking whether c occurs in T(b..e] (the symbol occurrence query). To date, no fully general structure achieving 𝒪(|G| log^𝒪(1) n) space and 𝒪(log^𝒪(1) n) query time is known. In this work, we establish new conditional lower bounds for frequency-related problems: - We prove that answering rank and symbol occurrence queries on grammar-compressed texts in polylogarithmic time using a 𝒪(|G| log^𝒪(1) n)-space structure that is constructible from the input grammar in 𝒪(|G| log^𝒪(1) n) time would imply an 𝒪(n² log^𝒪(1) n)-time algorithm for Boolean Matrix Multiplication (BMM), where the best known algorithms achieve 𝒪(n^{2.371339}) time. Our result is achieved using a more general lower bound for efficiently answering a batch of rank and symbol occurrence queries. - We generalize the above result, showing that even LZ78-compressed strings cannot support efficient rank queries. Since LZ78 is provably weaker than grammar compression, this yields a stronger result: rank and symbol occurrence queries remain hard for a wider class of compressors. We further show that achieving even additive approximations of rank queries would imply faster BMM algorithms. - After establishing hardness of rank and symbol occurrence queries, we consider a broader class of frequency-related queries and show that, under the popular Orthogonal Vectors (OV) conjecture, other problems, including range distinct counting and range mode frequency queries, also cannot be efficiently supported in compressed space. In summary, we develop new techniques for reasoning about computation over compressed data, and establish tight connections between compressed indexing and long-standing problems in fine-grained complexity. This sheds new light on compressed indexing by isolating a new class of frequency-related queries whose complexity hinges on known hard problems.