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 ... more >>>

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of O(p^{2}) under a random restriction that leaves each variable alive independently with probability p [SICOMP, 1998]. Using this result, he gave an \widetilde{\Omega}(n^{3}) formula size lower bound for the Andreev function, ... more >>>