Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIAMTION OF BOOLEAN FUNCTIONS:
Reports tagged with Approxiamtion of boolean functions:
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

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

ISSN 1433-8092 | Imprint