Beating Brute Force for Compression Problems

A compression problem is defined with respect to an efficient encoding function f; given a string x, our task is to find the shortest y such that f(y) = x. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time O(2ℓ · t(n)), where ℓ is the length of the shortest description y and t(n) is the time complexity of f when it prints n-bit output. We prove that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size 24 ℓ / 5 · poly(t(n)), which is significantly more efficient for all ℓ ≫ log(t(n)). Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length. As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2n can be solved by circuits of size 24/5 · w + o(w) · poly(2n), where w = s(n) log2(s(n) + n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) ≥ n. Similarly, the task of computing a short description of a string x when its t-complexity is at most ℓ, has circuits of size 24/5 ℓ · poly(t). We also give nontrivial circuits for computing Kt complexity on average, and for solving NP relations with “compressible” instance-witness pairs.