All Questions
2 questions
16
votes
3
answers
6k
views
Circuit complexity of Majority function
Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
- 679
1
vote
0
answers
189
views
Problems or issues with a proposed circuit class?
I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where ...
- 227