Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve

Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed forms, becomes more and more relevant. Suppose we are given a compression of size n of data that originally has size N, and we want to solve a problem with time complexity T(·). The naive strategy of “decompress-and-solve” gives time T(N), whereas “the gold standard” is time T(n): to analyze the compression as efficiently as if the original data was small. We restrict our attention to data in the form of a string (text, files, genomes, etc.) and study the most ubiquitous tasks. While the challenge might seem to depend heavily on the specific compression scheme, most methods of practical relevance (Lempel-Ziv-family, dictionary methods, and others) can be unified under the elegant notion of Grammar-Compressions. A vast literature, across many disciplines, established this as an influential notion for Algorithm design. We introduce a direly needed framework for proving (conditional) lower bounds in this field, allowing us to assess whether decompress-and-solve can be improved, and by how much. Our main results are: (1) The O(nN√(log N/n)) bound for LCS and the O(min{N log N, nM}) bound for Pattern Matching with Wildcards are optimal up to N o(1) factors, under the Strong Exponential Time Hypothesis. (Here, M denotes the uncompressed length of the compressed pattern.) (2) Decompress-and-solve is essentially optimal for ContextFree Grammar Parsing and RNA Folding, under the k-Clique conjecture. (3) We give an algorithm showing that decompress-and-solve is not optimal for Disjointness.

Authors

• Amir Abboud
• Arturs Backurs
• Karl Bringmann
• Marvin Künnemann

Keywords

• Time complexity
• Grammar
• Computer science
• Gold
• Standards
• Fine-grained Complexity
• Gold Standard
• Lower Bound
• Conjecture
• Pattern Matching
• Uncompressed
• RNA Folding
• Pattern Length
• Compression Scheme
• Context-free Grammar
• Upper Bound
• Classification Algorithms
• Computer Code
• Linear Time
• Matching Algorithm
• Algorithm For Problem
• Combination Of Algorithms
• Problem In Time
• Basic Problem
• Hamming Distance
• String Length
• Common Subsequence
• Tight Bound
• Edit Distance
• Central Problem
• Turing Machine
• Alphabet Size
• Text Length
• grammar-compression