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

Back to list of papers

Fooling Constant-Depth Threshold Circuits

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

Read the paper: ECCCFOCS proceedings

Abstract (for specialists)

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (\(\mathtt{LTF}\)) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth \(d\in\mathbb{N}\) and \(n^{1+\delta}\) wires, where \(\delta = 2^{-O(d)}\), using seed length \(O(n^{1-\delta})\) and with error \(2^{-n^{\delta}}\). This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for \(\mathtt{LTF}\) circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds.

Our second contribution is a PRG for De Morgan formulas of size \(s\) whose seed length is \(s^{1/3+o(1)} \cdot \mathrm{polylog}(1/\epsilon)\) for error \(\epsilon\). In particular, our PRG can fool formulas of sub-cubic size \(s=n^{3-\Omega(1)}\) with an exponentially small error \(\epsilon=\exp({-n^{\Omega(1)}})\). This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currently-known lower bounds for this class.

In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural "hybrid computational model" that combines several computational models. As part of our proofs we also construct "extremely low-error" PRGs for related circuit classes; for example, we construct a PRG for arbitrary functions of \(s\) \(\mathtt{LTF}\)s that can handle even the extreme setting of parameters \(s=n/\mathrm{polylog}(n)\) and \(\epsilon=2^{-n/\mathrm{polylog}(n)}\).

Not-so-abstract (for curious outsiders)

⚠️ This summary might gloss over some important details.

This paper is mainly about "threshold circuits", which can be thought of as a crude mathematical model of a brain. A threshold circuit is a network of "threshold gates" (analogous to neurons) connected by "wires" (analogous to axons). Each gate computes a weighted sum of its inputs; it outputs 0 or 1 depending on whether the weighted sum is above some threshold. (The reason we're interested in this model is that it comes up naturally in theoretical computer science, not because we're trying to understand actual brains, but still, it's nice to think of it as a brain.)

Our contribution is a "pseudorandom generator" for threshold circuits. In general, a pseudorandom generator is an algorithm that makes a few coin tosses and outputs a long sequence of bits that "appear random" in some sense. The output of our pseudorandom generator provably cannot be distinguished from a truly random sequence by any threshold circuit, assuming the circuit is "shallow" (i.e., paths from the input wires to the output wire are short) and assuming there aren't too many wires in total.

We posted a manuscript online in January 2021; Roei presented the paper at FOCS 2021 in February 2022. The FOCS proceedings version is merely an "extended abstract" with no proofs.

Expository material:

Video of my live Zoom presentation for the TCS+ Seminar (February 2021). Here are the slides from that presentation. I used very similar slides for a Zoom presentation at the Michigan-Purdue theory seminar (February 2021). See also these slides that I used for a Zoom presentation at the UT Austin theory seminar (April 2022).


An exposition of the paper is included in my PhD dissertation (Section 5.3).

Video of Roei's prerecorded presentation for FOCS (February 2022).