Exponential lower bound for bounded depth circuits with few threshold gates

We prove an exponential lower bound on the size of bounded depth circuits with O(logn) threshold gates computing an explicit function (namely, the parity function).Previously exponential lower bounds were known only for circuits with one threshold gate. Superpolynomial lower bounds are known for circuits with O(log2n) threshold gates.

► We study bounded depth circuits with small number of threshold gates. ► We are interested in exponential lower bounds on the size of such circuits. ► We prove a lower bound for circuits with O(logn) threshold gates computing parity. ► Previously such lower bounds were known only for circuits with one threshold gate.