Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 14 (2018) Article 9 pp. 1-55
CCC 2016 Special Issue
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Received: June 16, 2016
Revised: May 10, 2018
Published: June 5, 2018
Download article from ToC site:
[PDF (448K)] [PS (3305K)] [Source ZIP]
Keywords: complexity theory, circuit complexity, correlation bounds, threshold functions, random restrictions, learning, SAT
ACM Classification: F.1.2, F.2.3
AMS Classification: 68Q17, 68Q32

Abstract: [Plain Text Version]

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 εd>0 such that the Parity function on n bits has correlation at most nεd with depth-d threshold circuits which have at most n1+εd wires, and the Generalized Andreev function on n bits has correlation at most exp(nεd) with depth-d threshold circuits which have at most n1+ε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 AC0 circuits with no(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 AC0 with no(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.