<p>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:</p>

<p><a href="http://eccc.hpi-web.de/report/1995/041/">Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim. Optimal Bounds for the Approximation of Boolean Functions and Some Applications. ECCC, 1995.</a></p>

CC BY-SA 3.0
2012-05-08T00:50:12.593Z
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. =)
user6584
CC BY-SA 3.0
2012-05-08T00:38:44.163Z
2012-05-08T00:38:44.163Z
Ryan Williams
<p>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 &gt; 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$.</p>

<p>What is known if we are instead interested in <em>approximating</em> 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?</p>

<p>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} &lt; 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.</p>

<cc.complexity-theory><circuit-complexity>
Non-uniform hierarchy theorem for approximating functions
user6584
# Non-uniform hierarchy theorem for approximating functions

(Asked by: username_0 on 2012-05-07)

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 username_1'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.

**Tags:** cc.complexity-theory, circuit-complexity


---

## 1 answers

### Answer by username_1 on 2012-05-08. Score: 9 | Accepted answer

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.](http://eccc.hpi-web.de/report/1995/041/)

> **Comments:**
> **username_0**: 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. =)  

---

