The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
2answers
205 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 ...
8
votes
0answers
78 views

Depth of bounded fan-in circuits for unbounded fan-in circuits

Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$. What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size ...
20
votes
2answers
528 views

Bounded depth probability distributions

Two related questions about bounded depth computing: 1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
10
votes
2answers
206 views

Hierarchy theorems for circuit depth

What kind of hierarchy theorems are there for circuit depth? Statements like if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq ...
16
votes
1answer
542 views

Can we count in depth $\frac{\lg n}{\lg \lg n}$?

Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these ...