Depth-π Threshold Circuits vs. Depth-(π+1) AND-OR Trees
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell Β· 2023
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βΞ³.