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

Rajat De, Dominik Kempa

Grammar compression is a general compression framework in which a string $T$ of length $N$ is represented as a context-free grammar of size $n$ whose language contains only $T$. In…