Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-087 | 8th June 2022 02:43

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


Authors: Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Publication: 12th June 2022 05:57
Downloads: 258


For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed by any depth-$d$ $\text{TC}^0$ circuit with $n^{1 + \gamma}$ 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 $\text{AC}^0$ such as the parity function. Furthermore, in our result, the $\text{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^{-\gamma}$.

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 $\text{AC}^0$ (J. ACM, 2017). We show that under a modified version of their projection procedure, any depth-$d$ threshold circuit with $n^{1 + \gamma}$ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth $d + 1$ maintains structure.

ISSN 1433-8092 | Imprint