ISSN:
1420-8954
Keywords:
Circuit complexity
;
threshold circuits
;
modular counting
;
68Q05
;
68Q25
;
68Q40
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We study the power of constant-depth circuits containing negation gates, unbounded fan-in AND and OR gates, and a small number of MAJORITY gates. It is easy to show that a depth 2 circuit of sizeO(n) (wheren is the number of inputs) containingO(n) MAJORITY gates can determine whether the sum of the input bits is divisible byk, for any fixedk〉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 $$2^{n^{o(1)} } $$ containingn o(1) MAJORITY gates cannot determine if the sum of the input bits is divisible byk; moreover, such a circuit must give the wrong answer on a constant fraction of the inputs. This result was previously known only fork=2. We prove this by obtaining an approximate representation of the behavior of constant-depth circuits by multivariate complex polynomials.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01263421
