Mining Circuit Lower Bound Proofs for Meta-Algorithms

摘要

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for "easy" Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2 (n) ) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size . We get non-trivial compression for functions computable by AC (0) circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known.