<p>here are new results on this said to be the 1<sup>st</sup> in ~3 decades and some brief commentary</p>
<ul>
<li><p><a href="http://eccc.hpi-web.de/report/2015/166/" rel="noreferrer">A better-than-3n lower bound for the circuit complexity of an explicit function</a> / Find, Golovnev, Hirsch, Kulikov</p>
<blockquote>
<p>We consider Boolean circuits over the full binary basis. We prove a <span class="math-container">$(3+\frac{1}{86})n−o(n)$</span> lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the <span class="math-container">$3n−o(n)$</span> bound of Norbert Blum (1984).</p>
</blockquote>
</li>
<li><p><a href="https://mittheory.wordpress.com/2015/10/20/not-3n-anymore/" rel="noreferrer">Better Circuit Lower Bounds for Explicit Functions</a> / Ilya Razenshteyn, MIT CSAIL student blog</p>
</li>
</ul>

CC BY-SA 3.0
2015-10-20T15:22:47.620Z
2015-10-21T01:28:00.123Z
2020-06-17T09:38:08.363Z
vzn
<p>According to the paper <a href="http://dx.doi.org/10.1007/978-3-642-30870-3_44">A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function</a> by  Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and Savage.</p>

CC BY-SA 3.0
2014-03-06T14:58:30.137Z
2014-03-06T16:28:55.143Z
2014-03-06T16:28:55.143Z
Kristoffer Arnsfelt Hansen
<p>Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to <a href="https://cstheory.stackexchange.com/questions/7388/is-there-a-better-than-linear-lower-bound-for-factoring-and-discrete-log">this question</a> for related results.</p>

<p>What are the best known lower bounds if the range of $f$ is $\{0,1\}^m$?  In particular, do we get anything better for $m = n$, or for $m = 2$?</p>

CC BY-SA 3.0
2014-03-06T16:44:33.943Z
isnt this paper studying that? [On the One-Way Function Candidate Proposed by Goldreich](http://eccc.hpi-web.de/report/2012/175/) Cook et al
vzn
<circuit-complexity><lower-bounds>
Better lower bounds than 3n for non-boolean functions?
Manu
# Better lower bounds than 3n for non-boolean functions?

(Asked by: username_0 on 2014-03-06)

Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to [this question](https://cstheory.stackexchange.com/questions/7388/is-there-a-better-than-linear-lower-bound-for-factoring-and-discrete-log) for related results.

What are the best known lower bounds if the range of $f$ is $\{0,1\}^m$? In particular, do we get anything better for $m = n$, or for $m = 2$?

**Tags:** circuit-complexity, lower-bounds
> **Comments:**
> **username_1**: isnt this paper studying that? [On the One-Way Function Candidate Proposed by Goldreich](http://eccc.hpi-web.de/report/2012/175/) Cook et al  

---

## 2 answers

### Answer by username_2 on 2014-03-06. Score: 18 | Accepted answer

According to the paper [A $5n − o(n)$ Lower Bound on the Circuit Size over $U\_2$ of a Linear Boolean Function](http://dx.doi.org/10.1007/978-3-642-30870-3_44) by Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and Savage.


---

### Answer by username_1 on 2015-10-20. Score: 11

here are new results on this said to be the 1st in ~3 decades and some brief commentary

* [A better-than-3n lower bound for the circuit complexity of an explicit function](http://eccc.hpi-web.de/report/2015/166/) / Find, Golovnev, Hirsch, Kulikov

  > We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n−o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n−o(n)$ bound of Norbert Blum (1984).
* [Better Circuit Lower Bounds for Explicit Functions](https://mittheory.wordpress.com/2015/10/20/not-3n-anymore/) / Ilya Razenshteyn, MIT CSAIL student blog


---

