All reports by Author Jose Rolim:

__
TR95-041
| 28th June 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim#### Optimal Bounds for the Approximation of Boolean Functions and Some Applications

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

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 >>>