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

Our bound applies to any partial boolean function
and any ... more >>>