## A general lower bound for formula size of symmetric boolean functions

Recall that a boolean function $f:\{0,1\}^n\to\{0,1\}$ is symmetric if the value $f(x)$ only depends on the number $|x|$ of ones in $x$. Every such function corresponds to the function $f':\{0,1,\ldots,n\}\to\{0,1\}$ given by $f'(a)=1$ iff $f(x)=1$ for all $x$ of weight $|x|=a$.

Let $I_{n,d}$ denote the interval $\{\tfrac{n}{2}-d,\ldots,\tfrac{n}{2}+d\}$. Say that a symmetric boolean function $f(x)$ is $d$-trivial if either $f'$ is constant in the interval $I_{n,d}$, or $f'(a+1)\neq f'(a)$ for all $a \in I_{n,d}\setminus\{\tfrac{n}{2}+d\}$. Note that for every $d$, at most $4\cdot 2^{n+1-2d}$ of all $2^{n+1}$ symmetric functions can be $d$-trivial. Define $d(f)=\min\{d\colon \mbox{f is not d-trivial}\}.$ For example, if $f$ is the majority function, then $d(f)=1$. But if $f$ is the parity function, then $d(f)$ is maximal, is about $n/2$.

Let $k\geq 2$ be an arbitrary (but fixed) integer, and let $L(f)$ denote the smallest leaf-size of a formula computing $f$, with all boolean functions of $k$ variables allowed as gates.

Theorem (Cherukhin 2000): For every symmetric boolean function $f$ of $n$ variables, $L(f)=\Omega\Big(n\cdot \ln\frac{n}{d(f)} \Big).$
This extends Theorem 6.21 in the book to formulas using arbitrary boolean functions of larger number $k$ of variables (larger than $k=2$). Cherukhin's proof is also entirely different.

For example, if $f$ is the majority function, then $d(f)=1$, and we obtain $L(f)=\Omega(n\log n)$. But if $f$ is the parity function, then $d(f)$ is maximal, is about $n/2$, and we only obtain $L(f)=\Omega(n)$. This is not strange: formulas are allowed tu use arbitrary boolean functions of a constant number of variables, including $x\oplus y$, as gates.

Reference::

1. D. Yu. Cherukhin (2000): Lower bounds for the formula complexity of symmetric Boolean functions, Diskretn. Anal. Issled. Oper., Ser. 1, 7:3 (2000), 86-98. Paper (in Russian)

S. Jukna, April 2013