Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees

For any n ∈ ℕ and d = o(loglog(n)), we prove that there is a Boolean function F on n bits and a value γ = 2−Θ(d) such that F can be computed by a uniform depth-(d + 1) AC0 circuit with O(n) wires, but F cannot be computed by any depth-d TC0 circuit with n1 + γ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC0 such as the parity function. Furthermore, in our result, the AC0 circuit computing F is a monotone read-once formula (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n−γ.