Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ polynomials?)

  • $\begingroup$ The tribes function is an AND-OR tree, which is a linear size depth-2 linear threshold circuit. I don't see much room for a nontrivial lower bound... $\endgroup$ – Thomas Jun 29 '17 at 21:55
  • $\begingroup$ I guess by "depth 2 threshold circuit" you mean 2 layers of threshold gates. I am thinking of a single layer of threshold gates with a trivial summing gate at the top. $\endgroup$ – gradstudent Jun 29 '17 at 23:06
  • $\begingroup$ I clarified this in the question now! Thanks for pointing this out! $\endgroup$ – gradstudent Jun 29 '17 at 23:08
  • $\begingroup$ Are there any upper bounds in this model? i.e. can we rule out the possibility that no such circuit of any size computes the function? $\endgroup$ – Thomas Jun 29 '17 at 23:31
  • $\begingroup$ It depends on what you mean by a "trivial summing gate" ... if it's just a literally a sum of PTFs of degree one, then this is simulated by MAJORITY of THRESHOLD, for which lower bounds are well-known. (Although I'm not sure atm if the Tribes function is among them. If there were a polynomial size upper bound on the number of gates like what you seek, then probably the Orthogonal Conjecture is false, because it would mean that an OR of AND of OR can be simulated by a MAJORITY of THRESHOLD. Take a look at people.cs.uchicago.edu/~razborov/files/sign.pdf and the papers that cite it.) $\endgroup$ – Ryan Williams Jun 30 '17 at 0:38

Your Answer

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

Browse other questions tagged or ask your own question.