Name
Abstract | ||
|---|---|---|
In this paper we study the power of constant-depth circuits containing negation gates, unobunded fan-in AND and OR gates, and a small number of MAJORITY gates. It is easy to show that a depth 2 circuit of size O(n) (where n is the number of inputs) containing O(n) MAJORITY gates can determine whether the sum of the input bits is divisible by k, for any fixed k>1, whereas it is known that this requires exponentialsize circuits if we have no MAJORITY gates. Our main result is that a constant-depth circuit of size
2n °</font
>(1) 2^{n^{ \circ (1)} }
containing n
o(1)
MAJORITY gates cannot determine if the sum of the input bits is divisible by k. This result was previously known only for k=2. To prove it for general k, we view a circuit as computing a function from {1,,..., k–1}m into the complex numbers. We are then able to approximately represent the behavior of the circuit by a multivariate complex polynomial of low degree. We then prove the main theorem by showing that the function taking (x
1,..., x
m) {1,,..., k–1}m to x
1... x
m does not admit the required sort of polynomial approximation. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BF01263421 | Latin American Theoretical INformatics |
Keywords | DocType | Volume |
lower bound | Journal | 4 |
Issue | Citations | PageRank |
4 | 12 | 0.99 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David A. Mix Barrington | 1 | 856 | 94.79 |
| Howard Straubing | 2 | 528 | 60.92 |