<p>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?) </p>

CC BY-SA 3.0
2017-06-29T21:55:50.007Z
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...
Thomas Steinke
CC BY-SA 3.0
2017-06-29T23:06:57.903Z
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.
gradstudent
CC BY-SA 3.0
2017-06-29T23:08:17.980Z
I clarified this in the question now! Thanks for pointing this out!
gradstudent
CC BY-SA 3.0
2017-06-29T23:31:11.660Z
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?
Thomas Steinke
CC BY-SA 3.0
2017-06-30T00:38:51.320Z
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 http://people.cs.uchicago.edu/~razborov/files/sign.pdf and the papers that cite it.)
Ryan Williams
CC BY-SA 3.0
2017-06-30T01:27:46.677Z
Thanks for the comment! I guess when you say that "sum of PTF = MAJ of Th" you are thinking of the "sum" in the LHS as "sum mod 2". What if by "sum" I really mean that we can take sums over reals?
gradstudent
CC BY-SA 3.0
2017-06-30T05:14:13.560Z
@RyanWilliams Also isnt it likely to be true that Tribes function is exponentially hard for MAJ of Th?
gradstudent
CC BY-SA 3.0
2017-06-30T05:35:45.937Z
No, I mean sum over reals. Tribes is trivially computable with a Majority of Threshold, because Tribes is an AND of OR.
Ryan Williams
CC BY-SA 3.0
2017-06-30T14:09:55.057Z
Thanks - It seems then that my intuition is specifically of "Sum-of-Th". I was wondering if anything is known about hardness of Tribes for "Sum-Of-Th". (...also could you write a few lines about how that Razborov-Sherstov paper you linked is helping towards this - specifically in corollary 1.5 (on page 5) that paper seems to show lowerbounds on the sizes of the weights in the bottom layer of a Th-Of-Th circuit to compute AND-Of-OR-Of-AND. How is this to be interpreted as a circuit size lowerbound even for this function (which is not Tribes)? What am I missing?..)
gradstudent
CC BY-SA 3.0
2017-07-01T23:39:48.863Z
Thought of just stating that that as far as me (and some others I know) have tried the upperbound for implementing AND-of-k-ORs by Sum-Of-Threshold is exponentially large in "k". We don't know what is the smallest known implementation or of any lowerbound.
Student
<circuit-complexity><lower-bounds><boolean-functions><arithmetic-circuits>
Tribes function vs (modified) polynomial threshold circuits
gradstudent
# Tribes function vs (modified) polynomial threshold circuits

(Asked by: username_0 on 2017-06-29)

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?)

**Tags:** circuit-complexity, lower-bounds, boolean-functions, arithmetic-circuits

> **Comments:**
> **username_1**: 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...  
> **username_0**: 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.  
> **username_0**: I clarified this in the question now! Thanks for pointing this out!  
> **username_1**: 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?  
> **username_2**: 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 http://people.cs.uchicago.edu/~razborov/files/sign.pdf and the papers that cite it.)  
> **username_0**: Thanks for the comment! I guess when you say that "sum of PTF = MAJ of Th" you are thinking of the "sum" in the LHS as "sum mod 2". What if by "sum" I really mean that we can take sums over reals?  
> **username_0**: @RyanWilliams Also isnt it likely to be true that Tribes function is exponentially hard for MAJ of Th?  
> **username_2**: No, I mean sum over reals. Tribes is trivially computable with a Majority of Threshold, because Tribes is an AND of OR.  
> **username_0**: Thanks - It seems then that my intuition is specifically of "Sum-of-Th". I was wondering if anything is known about hardness of Tribes for "Sum-Of-Th". (...also could you write a few lines about how that Razborov-Sherstov paper you linked is helping towards this - specifically in corollary 1.5 (on page 5) that paper seems to show lowerbounds on the sizes of the weights in the bottom layer of a Th-Of-Th circuit to compute AND-Of-OR-Of-AND. How is this to be interpreted as a circuit size lowerbound even for this function (which is not Tribes)? What am I missing?..)  
> **username_3**: Thought of just stating that that as far as me (and some others I know) have tried the upperbound for implementing AND-of-k-ORs by Sum-Of-Threshold is exponentially large in "k". We don't know what is the smallest known implementation or of any lowerbound.  

---

## 0 answers

