Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-087 | 22nd November 2022 20:32

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

RSS-Feed




Revision #1
Authors: Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Accepted on: 22nd November 2022 20:32
Downloads: 672
Keywords: 


Abstract:

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}$.

At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for $\text{AC}^0$; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s 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.



Changes to previous version:

Revised exposition.


Paper:

TR22-087 | 8th June 2022 02:43

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





TR22-087
Authors: Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Publication: 12th June 2022 05:57
Downloads: 716
Keywords: 


Abstract:

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