## Highly differentiable boolean functions require super-linear DeMorgan formulas

A boolean function $f(x_1,\ldots,x_n)$ is $m$-*differentiable* ($m < n$) if for every assignment of constants $0/1$ to any subset of its $m$ variables, the resulting subfunction depends of all its remaining $n-m$ variables. Let $L(f)$ denote the smallest leaf-size of a
De Morgan formula computing $f$.
V.A. Malyshev (1967) proved the following lower bound.

If $f(x_1,\ldots,x_n)$ is $m$-differentiable, then
\[
L(f)\geq \frac{m}{2}\cdot \frac{\log_2 m}{\log_2\log_2 m}.
\]

**Reference:**