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

For n ∈ N and d = o(log log 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) AC 0 circuit with O(n) wires, but F cannot be computed by any depth-d TC 0 circuit with n 1+γ 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 AC 0 such as the parity function. Furthermore, in our result, the AC 0 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 -γ .

Our proof builds on the random projection procedure of Håstad, Rossman, Servedio, and Tan, which they used to prove the celebrated average-case depth hierarchy theorem for AC 0 (J. ACM, 2017). We show that under a modified version of their projection procedure, any depth-d threshold circuit with n 1+γ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.