All Questions
Tagged with circuit-depth boolean-formulas
2 questions
3
votes
0
answers
108
views
Do random functions have synchronous, alternating circuits with non-injective first layers?
After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
- 1,582
12
votes
0
answers
291
views
Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2
Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$...
