Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data

Computation over compressed data is a new paradigm in the design of algorithms and data structures, that can reduce the space usage and speed up the 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 such grammar is NP-hard, every polynomial time grammar compressor can be viewed as an approximation algorithm). Unfortunately, for the majority of grammar compressors, ρ is either unknown or satisfies ρ = ω(polylog N ): In their seminal paper, Charikar et al. [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 ).

In this paper, we develop the first technique for proving lower bounds for data structures and algorithms on grammars that is fully general and does not depend on the approximation ratio ρ of the used grammar compressor. Our first set of results concerns compressed data structures. In 2013, Verbin and Yu proved that implementing random access to T using a grammar constructed by an algorithm with ρ = O(polylog N ) requires Ω(log N/ log log N ) time in the worst case. This lower bound applies to any structure using O(n polylog N ) space and matches the existing upper bounds. We prove that this lower bound holds also for RePair, Greedy, LongestMatch, Sequential, and Bisection, while Ω(log log N ) time is required for random access to LZ78. Our lower bounds apply to any structure using O(n polylog N ) space and match the existing upper bounds. Moreover, our technique generalizes to classes of algorithms. Most notably, we tackle the notoriously hard to analyze class of global algorithms (that includes, e.g., the RePair algorithm) and show that the lower bound Ω(log N/ log log N ) applies to the whole class. This makes a significant step forward in a long-standing open problem of analyzing global algorithms; in the words of Charikar et al.: "Because they are so natural and our understanding is so incomplete, global algorithms are one of the most interesting topics related to the smallest grammar problem that deserves further investigation."

Our second set of results concerns compressed computation, i.e., computation that runs in time that depends on the size of the input in compressed form. Recently, Abboud, Backurs, Bringmann, and Künnemann [FOCS 2017 and NeurIPS 2020] proved numerous limitations of compressed computation under popular conjectures (such as SETH, k-Clique, k-OV, and k-SUM). Similarly as above, however, their framework also displays a dependence on ρ. For example, their results imply that, assuming the Combinatorial k-Clique Conjecture, there is no combinatorial algorithm to solve CFG Parsing (for which the best classical algorithm has a time complexity of O(N 3 )) on grammars constructed using Bisection (which satisfies ρ = Θ(N 1/2 )) that runs in O(n 3 • N ) or O(n 3/2 • N 2 ) time. The same is not known, however, for an algorithm running in O(n 5 • N ) or O(n 3 • N 2 ) time. Using our new techniques, we improve these and other conditional lower bounds. For example, for the CFG parsing on Bisection, we rule out an algorithms with runtime O(n c • N 3-ϵ ) for all constants c > 0 and ϵ > 0.