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 approximation degree, and thus completes the study of
booleanfunction approximation, introduced by Pippenger, concerning
circuit-size complexity. As a consequence, we provide the approximation
degree achieved by polynomial size circuits on a `random' boolean function;
that is
$$App_0(n,l(n) =n^k) = \Theta \left( \frac{\sqrt{ (n^k- n)}}{(2^{\frac n2}) } \right) \ , \: \: k >1.$$
As an application, we obtain a non trivial upper bound on the hardness function
$H(f)$ introduced by Nisan and Wigderson; that is, for any boolean function $f: \sEd^n \rightarrow \sEd$:
$$H(f)\ \le\ 2^{n/3}+n^2+O(1).$$
The optimal bound for $L(n,m,\epsilon)$ gives also a general
criterium for determining the quality of a given learning
algorithm for partial boolean functions.
The contribution in our proofs can be viewed as a new technique
based on some particular algebraic properties of linear operators
for approximating partial boolean functions.