Fooling Constant-Depth Threshold Circuits

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

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.