Computing Boolean functions by polynomials and threshold circuits

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