## Compression of Boolean Functions

### 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(2n) 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 2n/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:

• AC0,
• (de Morgan) formulas, and