Compression of Boolean Functions
Valentine Kabanets and Antonina Kolokolova
Abstract
We consider the problem of compression for ``easy'' Boolean functions: 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 2^{n}/n.
We get both positive and negative results. On the positive side, we show that several circuit classes for which lower bounds are proved by a method of random restrictions:
- AC^{0},
- (de Morgan) formulas, and
- (read-once) branching programs,
allow non-trivial compression for circuits up to the size for which lower bounds are known. On the negative side, we show that compressing functions from any class C⊆P/poly implies superpolynomial lower bounds against C for a function in NEXP; we also observe that compressing monotone functions of polynomial circuit complexity or functions computable by large-size AC^{0} circuits would also imply new superpolynomial circuit lower bounds.
Finally, we apply the ideas used for compression to get zero-error randomized #SAT-algorithms for de Morgan and complete-basis formulas, as well as branching programs, on n variables of about quadratic size that run in expected time 2^{n}/2^{nε}, for some ε>0 (dependent on the size of the formula/branching program).
Versions
- preliminary version in Electronic Colloquium on Computational Complexity ECCC-TR13-024.