We prove an optimal bound on the Shannon function
$L(n,m,\epsilon)$ which describes the trade-off between the
circuit-size complexity and the degree of approximation; that is
$$L(n,m,\epsilon)\ =\
\Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$
Our bound applies to any partial boolean function
and any ... more >>>