Average Case Lower Bounds for Bounded Depth Threshold Circuits

A threshold gate is a Boolean function that accepts its input based on whether some weighted linear combination of its inputs exceeds some fixed threshold value or not. A threshold circuit is a circuit made up of threshold gates. Proving superpolynomial lower bounds for depth-2 threshold circuits is one of the outstanding open problems in circuit complexity today.

Weak lower bounds for threshold circuits have been known for two decades. Impagliazzo, Paturi, and Saks (building on work of Paturi and
Saks) showed that any threshold circuit of depth-d computing the Parity function must have at least n^{1/(d-1)} gates and n^{1+1/exp(d)} wires. Surprisingly these bounds are known to be nearly tight.

We show stronger *average* case lower bounds in the same regime.  We show that for each integer d > 1, there is an epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most n^{1/2(d-1)} gates or n^{1+epsilon_d} wires. We also show that the Generalized Andreev Function has correlation at most 1/2^{n^{\Omega(1)}} with depth-d threshold circuits which have at most n^{1+ epsilon_d} wires.

I will talk about some of the techniques in this and other works on threshold circuits (joint work with Ruiwen Chen (Oxford) and Rahul Santhanam (Oxford)).