It is easy to show (by probabilistic argument) that there exist functions that require circuits of size $O(2^n/n)$. This, in turn, can be used to prove a non-deterministic hierarchy theorem showing (roughly) that if $2^n/n > T(n) \gg t(n)$ then there exist functions that can be computed by circuits of size $T$ but not by circuits of size $t$.

What is known if we are instead interested in approximating functions rather than computing them exactly? This question can be asked in many ways, but for concreteness let us say that $f \in approxSIZE(t)$ if there is a circuit family of size $t$ that (for each input length) computes $f$ correctly 3/4 of the time. What can be said about existence of hard functions here? What kind of hierarchy theorem is known? Does the answer change if we require the circuits to compute $f$ correctly $1-1/n$ of the time?

Note (added after Ryan Williams's answer): In fact, the answer to my first question follows from a simple modification of Shannon's lower bound, since a circuit on $n$ input bits can only $\epsilon$-approximate $\sum_{i=0}^{\epsilon \cdot 2^n} {2^n \choose i} < 2^{H(\epsilon) \cdot 2^n}$ functions, where $H$ denotes the binary entropy function. A hierarchy theorem should follow from this in the usual way.


There are some fairly tight results known for tradeoffs between circuit size and theirapproximation, with which one can prove hierarchy theorems for approximating functions. I would start with the following reference:

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

| cite | improve this answer | |
  • $\begingroup$ Thanks! This looks like exactly what I am looking for. I'm leaving the question open for now in case someone is aware of (1) a more recent reference, and/or (2) a statement of the results I am looking for so I don't have to go re-derive them myself. =) $\endgroup$ – user686 May 8 '12 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.