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.

Compressed indexing is a powerful technique that enables efficient querying over data stored in compressed form, significantly reducing memory usage and often accelerating computation. While extensive progress has been made for one-dimensional strings, many real-world datasets (such as images, maps, and adjacency matrices) are inherently two-dimensional. Unfortunately, naively applying 1D techniques to 2D data leads to suboptimal results, as fundamental structural repetition is lost during linearization. This motivates the development of native 2D compressed indexing methods that preserve both compression and query efficiency.

Word Break is a prototypical factorization problem in string processing: Given a word$w$of length$N$and a dictionary$\mathcal{D}=\{d_{1},\ d_{2},\ \ldots,\ d_{K}\}$of$K$strings, determine whether we can partition$w$into words from$\mathcal{D}$. We propose the first algorithm that solves the Word Break problem over the SLP-compressed input text$w$. Specifically, we show that, given the string$w$represented using an SLP of size$g$we can solve the Word Break problem in$\mathcal{O}(g\cdot m^{\omega}+M)$time, where$m=\max_{i=1}^{K}\vert d_{i}\vert M=\sum_{i=1}^{K}\vert d_{i}\vert$, and$\omega\geq 2$is the matrix multiplication exponent. We obtain our algorithm as a simple corollary of a more general result: We show that in$\mathcal{O}(g\cdot m^{\omega}+M)$time, we can index the input text$w$so that solving the Word Break problem for any of its substrings takes$\mathcal{O}(m^{2}\log N)$time (independent of the substring length). Our second contribution is a lower bound: We prove that, unless the Combinatorial$k$-Clique Conjecture fails, there is no combinatorial algorithm for Word Break on SLP-compressed strings running in$\mathcal{O}(g\cdot m^{2-\epsilon}+M)$time for any$\epsilon > 0$.

Computation over compressed data is a new paradigm in the design of algorithms and data structures that can reduce space usage and speed up computation by orders of magnitude. One of the most frequently employed compression frameworks, capturing many practical compression methods (such as the Lempel-Ziv family, dictionary methods, and others), is grammar compression. In this framework, a string T of length N is represented as a context-free grammar of size n whose language contains only the string T. In this paper, we focus on studying the limitations of these techniques. Previous work focused on proving lower bounds for algorithms and data structures operating over grammars constructed using algorithms that achieve the approximation ratio ρ = O (polylog N) (since finding the smallest grammar representation is NP-hard, every polynomial-time grammar compressor can be viewed as an approximation algorithm). Unfortunately, for many grammar compressors we either have ρ = ω (polylog N) or it is not known whether ρ = O(polylog N) holds. In their seminal paper, Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, and Shelat [IEEE Trans. Inf. Theory 2005] studied seven popular grammar compression algorithms: RePair, Greedy, LongestMatch, Sequential, Bisection, LZ78, and α-Balanced. Only one of them (α-Balanced) is known to achieve ρ = O(polylog N).