<p>It is well known that lower bounds on circuits implies lower bounds on time complexity, just because circuits can efficiently simulate algorithms. </p>

<p>By the continuous work started by Ryan Williams, we know that upper bounds on the algorithms can imply circuit lower bounds [1].</p>

<p>Another connection between uniform and non-uniform complexities is that there exist algorithms that uses efficient circuits to gain a speed up. For example, first subquadratic algorithm for 3-sum [2] uses efficient decision trees. </p>

<p>I'm looking for results in the direction I haven't discussed yet: can lower bounds for time complexity imply lower bounds for circuit complexity. It is worth mentioning that algorithms that uses efficient circuits are taking advantage of the actual constructions rather then pure existence.</p>

<p>[1] Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams.</p>

<p>[2]Threesomes, Degenerates, and Love Triangles. Allan Grønlund, Seth Pettie</p>

CC BY-SA 3.0
2017-04-11T23:24:06.683Z
By Karp-Lipton theorem, if $NP \subseteq P/poly$ then $\Sigma_2 = \Pi_2$. Thus, a lower bound that shows that $\Sigma_2 \ne \Pi_2$ would imply $NP \not\subseteq P/poly$.
Or Meir
CC BY-SA 3.0
2017-04-12T03:01:30.437Z
@OrMeir: Those are two great examples, which seem like perfectly good answers!
Joshua Grochow
CC BY-SA 3.0
2017-04-12T03:37:03.557Z
In general, Karp-Lipton-type theorems have the form: "circuit upper bound implies uniform upper bound" ... although I have the feeling Ivan meant something more concrete, where a time lower bound for a problem $\Pi$ implies a circuit lower bound for the same problem $\Pi$. Even so, NEXP != EXP implies NEXP not in P/poly is pretty solid!
Ryan Williams
CC BY-SA 3.0
2017-04-12T05:33:16.003Z
Those are really good examples! Indeed I would rather have an example of lower bound transfer from uniform world to non-uniform for the same problem, but  this is close enough.
ivmihajlin
<cc.complexity-theory><circuit-complexity>
Non-uniform lower bounds from uniform
ivmihajlin
# Non-uniform lower bounds from uniform

(Asked by: username_0 on 2017-04-11)

It is well known that lower bounds on circuits implies lower bounds on time complexity, just because circuits can efficiently simulate algorithms.

By the continuous work started by Ryan Williams, we know that upper bounds on the algorithms can imply circuit lower bounds [1].

Another connection between uniform and non-uniform complexities is that there exist algorithms that uses efficient circuits to gain a speed up. For example, first subquadratic algorithm for 3-sum [2] uses efficient decision trees.

I'm looking for results in the direction I haven't discussed yet: can lower bounds for time complexity imply lower bounds for circuit complexity. It is worth mentioning that algorithms that uses efficient circuits are taking advantage of the actual constructions rather then pure existence.

[1] Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams.

[2]Threesomes, Degenerates, and Love Triangles. Allan Grønlund, Seth Pettie

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: By Karp-Lipton theorem, if $NP \subseteq P/poly$ then $\Sigma_2 = \Pi_2$. Thus, a lower bound that shows that $\Sigma_2 \ne \Pi_2$ would imply $NP \not\subseteq P/poly$.  
> **username_2**: @OrMeir: Those are two great examples, which seem like perfectly good answers!  
> **username_3**: In general, Karp-Lipton-type theorems have the form: "circuit upper bound implies uniform upper bound" ... although I have the feeling Ivan meant something more concrete, where a time lower bound for a problem $\Pi$ implies a circuit lower bound for the same problem $\Pi$. Even so, NEXP != EXP implies NEXP not in P/poly is pretty solid!  
> **username_0**: Those are really good examples! Indeed I would rather have an example of lower bound transfer from uniform world to non-uniform for the same problem, but  this is close enough.  

---

## 0 answers

