<p>In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$2^n/n^3$$. </p>

<p>So the answer to question 2 is "yes"</p>

<p>Since random functions need large threshold circuits, question 1 seems to be effectively asking "does $P \neq NP$ imply TRUE" so the answer should also be "yes", since both TRUE and FALSE imply TRUE.</p>

CC BY-SA 3.0
2017-10-05T05:27:18.730Z
Thanks! I guess I am not understanding how your paper's argument answers my question 1. In my question 1 I am not constraining the depth of the LTF or PTF circuit to be 2 as is required for your argument above. Maybe those functions which are exponentially hard for depth 2 LTFs become polynomial sized for higher depth LTFs? (..also my separate question below the dotted line was as to what is the largest/strongest basis of gates over which one expects exponential size lower bounds if $P \neq NP$ - can this basis include LTF/PTFs with or without some weight restriction..)
gradstudent
CC BY-SA 3.0
2017-10-05T07:20:39.133Z
There are at most $2^{k^2}$ linear threshold functions on $k$ variables. Thus a Shannon-style counting lower bound shows that there exists a Boolean function on $n$ variables requiring threshold circuits of size $2^{\Omega(n)}$ regardless of the depth.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-10-05T04:44:08.810Z
2017-10-05T04:44:08.810Z
Ryan Williams
<p>(I am hugely editing the question. My initial question was if lowerbounds on threshold circuits say anything about P/NP and it seems that they dont. Irrespective of P/NP its an independently true fact that there exists Boolean functions which are exponentially hard for threshold circuits just that we have never seen them.)</p>

<p>Let me ask my followup question in $3$ parts which I guess are related,</p>

<ol>
<li><p>If one looks at the space of all polynomial sized threshold circuits (at constant depth or not) then do we know of any natural complexity class in which they sit? The closest I know of is that the class of depth 3 threshold circuits with no weight restriction are known to be in $NP/poly$. What happens at higher or non-constant depths? </p></li>
<li><p>Is there any class of circuits against which we know that there cannot be exponentially hard functions if $P=NP$? (Threshold circuits are clearly not of this type.)</p></li>
<li><p>Are there reasons to believe that for each depth $d$ there exists a Boolean function which is easy for depth $d+1$ but exponentially hard for depth $d$? And if such functions are found then would it have any implications (separations) for the other usual complexity classes? </p></li>
</ol>

CC BY-SA 3.0
2017-10-05T01:32:36.437Z
Could you kindly elaborate on the connection between P/poly  and my question?
gradstudent
CC BY-SA 3.0
2017-10-05T01:48:17.027Z
So is any kind of threshold circuit (with or without weight restriction on a subset of the layers) known to be in P/poly? Or how does this help answer my first 2 questions? (..the closest thing to your comment that I am aware of is that depth $3$ threshold circuits with polynomially bounded integral weights is the largest threshold circuit class known to be contained inside $NP/poly$...)
gradstudent
CC BY-SA 3.0
2017-10-05T02:01:23.823Z
What do you mean by "simple"? So you think that if $P \neq NP$ then there would also be a gap between $NP$ and $P/ poly$ and hence there will be a Boolean function which is exponentially hard for threshold circuits with "simple" weights?
gradstudent
CC BY-SA 3.0
2017-10-05T06:40:35.897Z
Polynomial-size circuits with *arbitrary* threshold gates can be computed by polynomial-size circuits over De Morgan basis.
Emil Jeřábek
CC BY-SA 3.0
2017-10-05T06:55:18.217Z
Any reference where the proof can be read up quickly? I am aware of this closeby result : In this paper  https://link.springer.com/chapter/10.1007%2F11549345_11 
it was shown that general weight threshold gates can be computed by polynomial size depth 2 circuits built from majority gates. Then we can just compute each of these majorities by constant depth circuits built from AND and OR gates. So any threshold gate can be simulated by constant depth exponential size AND-OR circuits.
gradstudent
CC BY-SA 3.0
2017-10-05T06:57:21.243Z
Why has someone voted to close this question!? Anything wrong with the question?
gradstudent
CC BY-SA 3.0
2017-10-05T08:04:59.657Z
Your link is the one that proves it. Of course, majority has polynomial-size AND-OR circuits. These are all basic facts, which is also why I voted to close the question: it is not research level, it would be more suitable for cs.stackexchange.com .
Emil Jeřábek
CC BY-SA 3.0
2017-10-05T12:09:36.743Z
Now that I am in the office, I see that the paper you linked to is something recent. The result is in fact classical, see https://link.springer.com/article/10.1007/BF01200426 .
Emil Jeřábek
CC BY-SA 3.0
2017-10-06T01:12:34.167Z
I have changed the question a lot to make it more cognizant of the things pointed out here.
gradstudent
CC BY-SA 3.0
2017-10-06T15:48:06.353Z
Question 1 still does not reflect what has been pointed out in the comments. Polynomial-size circuits with arbitrary threshold gates of arbitrary depth are in P/poly.
Emil Jeřábek
CC BY-SA 3.0
2017-10-06T20:30:59.870Z
Yes, but I am referring to the fact that I have seen stated in one recent paper that apparently depth $3$ LTFs are contained in $NP/poly$. How are these two things related and how does this statement change for depths $4,5,..$ or any constant depths? I don't understand why these papers want to think of the universe as $NP/poly$ when $P/poly \subseteq NP/poly$ and hence by what you say it seems that a stronger statement is known.
gradstudent
<cc.complexity-theory><circuit-complexity><circuit-families><circuits>
Some questions about the depth hierarchy for threshold circuits
gradstudent
# Some questions about the depth hierarchy for threshold circuits

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

(I am hugely editing the question. My initial question was if lowerbounds on threshold circuits say anything about P/NP and it seems that they dont. Irrespective of P/NP its an independently true fact that there exists Boolean functions which are exponentially hard for threshold circuits just that we have never seen them.)

Let me ask my followup question in $3$ parts which I guess are related,

1. If one looks at the space of all polynomial sized threshold circuits (at constant depth or not) then do we know of any natural complexity class in which they sit? The closest I know of is that the class of depth 3 threshold circuits with no weight restriction are known to be in $NP/poly$. What happens at higher or non-constant depths?
2. Is there any class of circuits against which we know that there cannot be exponentially hard functions if $P=NP$? (Threshold circuits are clearly not of this type.)
3. Are there reasons to believe that for each depth $d$ there exists a Boolean function which is easy for depth $d+1$ but exponentially hard for depth $d$? And if such functions are found then would it have any implications (separations) for the other usual complexity classes?

**Tags:** cc.complexity-theory, circuit-complexity, circuit-families, circuits
> **Comments:**
> **username_0**: Could you kindly elaborate on the connection between P/poly  and my question?  
> **username_0**: So is any kind of threshold circuit (with or without weight restriction on a subset of the layers) known to be in P/poly? Or how does this help answer my first 2 questions? (..the closest thing to your comment that I am aware of is that depth $3$ threshold circuits with polynomially bounded integral weights is the largest threshold circuit class known to be contained inside $NP/poly$...)  
> **username_0**: What do you mean by "simple"? So you think that if $P \neq NP$ then there would also be a gap between $NP$ and $P/ poly$ and hence there will be a Boolean function which is exponentially hard for threshold circuits with "simple" weights?  
> **username_1**: Polynomial-size circuits with *arbitrary* threshold gates can be computed by polynomial-size circuits over De Morgan basis.  
> **username_0**: Any reference where the proof can be read up quickly? I am aware of this closeby result : In this paper  https://link.springer.com/chapter/10.1007%2F11549345_11  it was shown that general weight threshold gates can be computed by polynomial size depth 2 circuits built from majority gates. Then we can just compute each of these majorities by constant depth circuits built from AND and OR gates. So any threshold gate can be simulated by constant depth exponential size AND-OR circuits.  
> **username_0**: Why has someone voted to close this question!? Anything wrong with the question?  
> **username_1**: Your link is the one that proves it. Of course, majority has polynomial-size AND-OR circuits. These are all basic facts, which is also why I voted to close the question: it is not research level, it would be more suitable for cs.stackexchange.com .  
> **username_1**: Now that I am in the office, I see that the paper you linked to is something recent. The result is in fact classical, see https://link.springer.com/article/10.1007/BF01200426 .  
> **username_0**: I have changed the question a lot to make it more cognizant of the things pointed out here.  
> **username_1**: Question 1 still does not reflect what has been pointed out in the comments. Polynomial-size circuits with arbitrary threshold gates of arbitrary depth are in P/poly.  
> **username_0**: Yes, but I am referring to the fact that I have seen stated in one recent paper that apparently depth $3$ LTFs are contained in $NP/poly$. How are these two things related and how does this statement change for depths $4,5,..$ or any constant depths? I don't understand why these papers want to think of the universe as $NP/poly$ when $P/poly \subseteq NP/poly$ and hence by what you say it seems that a stronger statement is known.  

---

## 1 answers

### Answer by username_2 on 2017-10-05. Score: 2

In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$2^n/n^3$$.

So the answer to question 2 is "yes"

Since random functions need large threshold circuits, question 1 seems to be effectively asking "does $P \neq NP$ imply TRUE" so the answer should also be "yes", since both TRUE and FALSE imply TRUE.

> **Comments:**
> **username_0**: Thanks! I guess I am not understanding how your paper's argument answers my question 1. In my question 1 I am not constraining the depth of the LTF or PTF circuit to be 2 as is required for your argument above. Maybe those functions which are exponentially hard for depth 2 LTFs become polynomial sized for higher depth LTFs? (..also my separate question below the dotted line was as to what is the largest/strongest basis of gates over which one expects exponential size lower bounds if $P \neq NP$ - can this basis include LTF/PTFs with or without some weight restriction..)  
> **username_3**: There are at most $2^{k^2}$ linear threshold functions on $k$ variables. Thus a Shannon-style counting lower bound shows that there exists a Boolean function on $n$ variables requiring threshold circuits of size $2^{\Omega(n)}$ regardless of the depth.  

---

