Fooling Constant-Depth Threshold Circuits (Extended Abstract)

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 (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 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\text{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$ LTFs that can handle even the extreme setting of parameters $s=n/\text{polylog}(n)$ and $\epsilon=2^{-n/\text{polylog}(n)}$.

Authors

• Pooya Hatami
• William M. Hoza
• Avishay Tal
• Roei Tell

Keywords

• Computer science
• Computational modeling
• Wires
• Generators
• Complexity theory
• Integrated circuit modeling
• Deterministic
• Lower Bound
• Parameter Settings
• Probability Of Failure
• Constant Depth
• Size Formula
• Restrictive Procedures
• Linear Threshold
• Classical Circuit
• High Probability
• Running Time
• Functional Form
• Functional Class
• Proof Of Theorem
• Hybrid Model
• Fraction Of Variance
• Communication Protocol
• Choice Of Variables
• Small Probability
• High-level Overview
• Kept Alive
• Number Of Wires
• Monomial
• Subsequent Iterations
• Technical Results
• Polytope
• Acceptance Probability
• Explicit Function
• pseudorandom generators
• threshold circuits
• De Morgan formulas