Complex polynomials and circuit lower bounds for modular counting

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 \(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 ₁,..., x _m) ∈ {1,ω,..., ω^k−1}^m to x ₁... x _m does not admit the required sort of polynomial approximation.

Authors and Affiliations

1. Department of Computer and Information Science, University of Massachusetts, 01003, Amherst, Massachusetts, USA

   David A. Mix Barrington

2. Computer Science Department, Boston College, 02167, Chestnut Hill, Massachussets, USA

   Howard Straubing

Reprints and permissions

© 1992 Springer-Verlag Berlin Heidelberg

Policies and ethics