We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an n-variate Boolean function f computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time \poly(2^n) a circuit C (no restriction on the type of C) computing f so ... more >>>

We give a function h:\{0,1\}^n\to\{0,1\} such that every deMorgan formula of size n^{3-o(1)}/r^2 agrees with h on at most a fraction of \frac{1}{2}+2^{-\Omega(r)} of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function f:\{0,1\}^n\to\{1,-1\} computable by a de Morgan formula of size s, we show that
\[
\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ... more >>>

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is 2. Namely, we show that for any Boolean function f: \{-1,1\}^n \to \{-1,1\}, setting each variable out of x_1, \ldots, x_n with probability 1-p to a randomly chosen constant, reduces the expected formula size ... more >>>

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula F of size at most n^{3-16\epsilon} in time 2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n), for any small constant \epsilon>0. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>