Volume 14 (2018) Article 17 pp. 1-25

New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates

by R. Ryan Williams

Received: June 28, 2015
Revised: June 4, 2018
Published: December 10, 2018

$ \newcommand \poly {{\operatorname{poly}}} \newcommand \SYM {{\sf SYM}} \newcommand \THR {{\sf THR}} \newcommand \ACC {{\sf ACC}} \newcommand \NEXP {{\sf NEXP}} \newcommand \eps {{\varepsilon}} $

Let $\ACC \circ \THR$ be the class of constant-depth circuits comprised of AND, OR, and MOD $m$ gates (for some constant $m > 1$), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a “midpoint” between $\ACC$ (where we know nontrivial lower bounds) and depth-two linear threshold circuits (where nontrivial lower bounds remain open). We give an algorithm for evaluating an arbitrary symmetric function of $2^{n^{o(1)}}$ $\ACC \circ \THR$ circuits of size $2^{n^{o(1)}}$, on all possible inputs, in $2^n \cdot \poly(n)$ time. Several consequences are derived:

The number of satisfying assignments to an $\ACC\circ\THR$ circuit of $2^{n^{o(1)}}$ size is computable in $2^{n-n^{\eps}}$ time (where $\eps > 0$ depends on the depth and modulus of the circuit).

$\NEXP$ does not have quasi-polynomial size $\ACC \circ \THR$ circuits, and $\NEXP$ does not have quasi-polynomial size $\ACC \circ \SYM$ circuits. Nontrivial size lower bounds were not known even for ${\sf AND} \circ {\sf OR} \circ \THR$ circuits.

Every 0-1 integer linear program with $n$ Boolean variables and $s$ linear constraints is solvable in $2^{n-\Omega(n/\log^4(sM(\log n)))}\cdot \poly(s,n,M)$ time with high probability, where $M \leq 2^{n^{o(1)}}$ is an upper bound on the bit complexity of the coefficients. (For example, 0-1 integer programs with weights in $[-2^{n^{o(1)}},2^{n^{o(1)}}]$ and $\poly(n)$ constraints can be solved in $2^{n-\Omega(n/\log^4 n)}$ time.)

We also present an algorithm for evaluating depth-two linear threshold circuits (also known as $\THR \circ \THR$) with exponential weights and $2^{n/24}$ size on all $2^n$ input assignments, running in $2^n \cdot \poly(n)$ time. This is evidence that non-uniform lower bounds for $\THR \circ \THR$ are within reach.

DOI: 10.4086/toc.2018.v014a017

© 2018 R. Ryan Williams
Licensed under a Creative Commons Attribution License (CC-BY)