# LTF circuits and $AC^0$

Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).

For any vector $w \in \mathbb{R}^n$ and any number $c \in \mathbb{R}$ we define the LTF (x) gate as the function, $\{0,1\}^n \rightarrow \{0,1\}$ such that $LTF(x) =0$ if $c + \vec{w}.\vec{x} \leq 0$ or else $LTF(x) = 1$.

• Personally I suggest that giving the definition of linear threshold circuits would make the question more self-contained. Oct 18 '17 at 21:56
• I have put in the definition. Oct 18 '17 at 22:27

In the case of unbounded weights, we don't have any superpolynomial lower bounds. The best known lower bound for unrestricted depth two threshold circuits due to Kane and Williams, is $\Omega(n^{3/2})$.
• Thanks! (I have read that Kane-Williams paper) (1) Is this formally stated as a conjecture anywhere that polynomial sized polynomially bounded weight constant depth $LTF$ cannot capture $AC^0$. That would be very helpful! (2) So you think that even with unbounded weights and unboundd size constant depth LTFs cant capture all of $AC^0$? Could you kindly state your first conjecture a bit more precisely? Oct 19 '17 at 15:29
• Thanks! I am getting confused by your phrase "constant-depth threshold circuits". What restrictions are you putting on the weights and the size? Its somewhat believable that poly-sized poly-weight constant depth LTFs cant capture all of $AC^0$. But if you allow for either either size or weights or both to be unbounded then it looks very surprising if depth 2 LTF still continues to be weaker than $AC^0$. (..We already know from Allender's (FOCS 1989) result that quasi-polynomial depth 3 Majority gets all of $AC^0$..) Oct 19 '17 at 15:36
• We are always interested in polysize circuits. Regarding weights, it's known that polysize depth-$d$ threshold circuits with arbitrary weights can be simulated by polysize depth-$d+1$ threshold circuits with polynomial weights, so it doesn't really matter. Oct 19 '17 at 15:44
• Yes, but I guess its possible that with poly-size weight and with exponential/super-polynomial size depth 2 LTF gets all of $AC^0$. I cant see anything ruling this out and proving this is possibly not at all trivial... Oct 19 '17 at 15:49