A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
Wolfgang J. Paul · SIAM Journal on Computing · 1977
Consider the combinational complexity $L(f)$ of Boolean functions over the basis $\Omega = \{ f|f:\{ 0,1\} ^2 \to \{ 0,1\} \} $. A new method for proving linear lower bounds of size $2n$ is presented. Combining it with methods presented in Savage [13, (1974)] and Schnorr [18, (1974)], we establish for a special sequence of functions $f_n :\{ 0,1\} ^{n + 2\log (n) + 1} \to \{ 0,1\} :2.5n \leqq L(f) \leqq 6n$. Also a trade-off result between circuit complexity and formula size is derived.