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$.

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

I doubt that AC0 can be captured by constant depth threshold circuits, but this hasn't been proved. In the case of small weights, perhaps existing methods suffice to rule out all of AC0 being captured by depth 2 threshold circuits. See Razborov's survey for several pointers, include exponential lower bounds for functions which, unfortunately, are beyond AC0

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})$.

  • $\begingroup$ 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? $\endgroup$ – gradstudent Oct 19 '17 at 15:29
  • $\begingroup$ I'm not aware of such a conjecture being explicitly stated, though perhaps you can find such a conjecture in the literature. Presumably either a Sipser function or a "random" function in AC0 of high enough depth will be hard for constant-depth threshold circuits. $\endgroup$ – Yuval Filmus Oct 19 '17 at 15:31
  • $\begingroup$ 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$..) $\endgroup$ – gradstudent Oct 19 '17 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 19 '17 at 15:44
  • $\begingroup$ 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... $\endgroup$ – gradstudent Oct 19 '17 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.