Computing Boolean functions by polynomials and threshold circuits (Q1293360)

The authors investigate the computational complexity of threshold circuits for Boolean functions. A function with small size unbounded weight threshold-AND circuits is presented 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. The authors also show that unbounded weight threshold gates cannot simulate alternation. Three open problems are formulated.