Theory of Computing
-------------------
Title : Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Authors : Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Volume : 14
Number : 9
Pages : 1-55
URL : https://theoryofcomputing.org/articles/v014a009
Abstract
--------
We show average-case lower bounds for explicit Boolean functions
against bounded-depth threshold circuits with a superlinear number of
wires. We show that for each integer $d > 1$, there is a constant
$\varepsilon_d > 0$ such that the Parity function on $n$ bits has
correlation at most $n^{-\varepsilon_d}$ with depth-$d$ threshold
circuits which have at most $n^{1+\varepsilon_d}$ wires, and the
Generalized Andreev function on $n$ bits has correlation at most
$\exp(-{n^{\varepsilon_d}})$ with depth-$d$ threshold circuits which
have at most $n^{1+\varepsilon_d}$ wires. Previously, only worst-case
lower bounds in this setting were known (Impagliazzo, Paturi, and Saks
(SICOMP 1997)).
We use our ideas to make progress on several related questions. We
give satisfiability algorithms beating brute force search for
depth-$d$ threshold circuits with a superlinear number of wires. These
are the first such algorithms for depth greater than 2. We also show
that Parity on $n$ bits cannot be computed by polynomial-size
$\textsf{AC}^0$ circuits with $n^{o(1)}$ _general_ threshold gates.
Previously no lower bound for Parity in this setting could handle more
than $\log(n)$ gates. This result also implies subexponential-time
learning algorithms for $\textsf{AC}^0$ with $n^{o(1)}$ threshold
gates under the uniform distribution. In addition, we give almost
optimal bounds for the number of gates in a depth-$d$ threshold
circuit computing Parity on average, and show average-case lower
bounds for threshold formulas of _any_ depth.
Our techniques include adaptive random restrictions, anti-
concentration and the structural theory of linear threshold functions,
and bounded-read Chernoff bounds.
A conference version of this paper appeared in the Proceedings
of the 31st Conference on Computational Complexity, 2016.