Computing Boolean functions by polynomials and threshold circuits

We investigate the computational power of threshold—AND circuits versus threshold—XOR circuits. In contrast to the observation that small weight threshold—AND circuits can be simulated by small weight threshold—XOR circuit, we present a function with small size unbounded weight threshold—AND circuits for which all threshold—XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold gates cannot simulate alternation: There are \( AC^{0,3} \)-functions which need exponential size threshold—AND circuits.

Authors and Affiliations

1. Theoretische Informatik, Universität Mannheim—A5, D-68131 Mannheim, Germany, e-mail: krause@pi3.informatik.uni-mannheim.de, , , , , , DE

   M. Krause

2. Mathematical Institute, Academy of Sciences of Czech Republik, Žitná 25, 115 67 Praha 1, Czech Republic, e-mail: pudlak@math.cas.cz, , , , , , CS

   P. Pudlák

Received: August 8, 1996.

Reprints and permissions