\(\renewcommand{\epsilon}{\varepsilon}\) \(\renewcommand{\hat}{\widehat}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\)

Back to list of papers


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

By Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell


Read the paper: ECCC

Abstract (for specialists)

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)\) \(\mathsf{AC}^0\) circuit with \(O(n)\) wires, but \(F\) cannot be computed by any depth-\(d\) \(\mathsf{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 \(\mathsf{AC}^0\) such as the parity function. Furthermore, in our result, the \(\mathsf{AC}^0\) circuit computing \(F\) is a monotone read-once formula (i.e., an \({\mathsf{AND}\text{-}\mathsf{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 \(\mathsf{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 \({\mathsf{AND}\text{-}\mathsf{OR}}\) tree of depth \(d + 1\) maintains structure.

Not-so-abstract (for curious outsiders)

⚠️ This summary might gloss over some important details.

A "Boolean circuit" is an idealized network of logic gates and input variables connected by wires. You can assign binary values to the input variables. The values feed into whatever gates are connected to the variables. The outputs of those gates feed into other gates, which feed into other gates, and so on, until eventually the circuit produces a binary output.

In one basic circuit model, the only available logic gates are "AND" gates and "OR" gates. (An "AND" gate outputs 1 if its inputs are all 1. An "OR" gate outputs 1 if at least one of its inputs is 1.) There is also a more powerful circuit model in which we allow "threshold gates," which compute an arbitrary weighted sum of their input bits and output 1 if the weighted sum is above some threshold. This second type of circuit can be considered a simplified model of a brain.

What are threshold gates good for? How much additional power do they give you compared to AND/OR gates? It has been known for decades that using threshold gates, it is possible to decrease the depth of a given AND/OR circuit. (The "depth" of a circuit is the length of the longest path from input to output, which can be considered a measure of the amount of time that the computation takes.)

The caveat is that known depth-reduction methods substantially increase the total number of wires in the circuit, which is a measure of the total amount of work that goes into the computation. In our paper, we prove that increasing the number of wires is unavoidable in general. That is, we prove that decreasing the depth of certain AND/OR circuits using threshold gates requires increasing the number of wires by a non-negligible amount.

We posted a manuscript online in June 2022.


Expository material:

Slides from my presentation at TOCA-SV (May 2022). See also this poster that I presented at TOCA-SV the same day.