pdf icon
Volume 14 (2018)
Article 17 pp. 1-25
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates
Received: June 28, 2015
Revised: June 4, 2018
Published: December 10, 2018
Keywords: circuit complexity, satisfiability algorithms, linear threshold functions
ACM Classification: F.1.1, F.2.3, G.1.6
AMS Classification: 68Q15, 68Q17, 68Q15
Abstract:
[Plain Text Version]
$
\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.