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
Download article from ToC site:
[PDF (347K)] [PS (1870K)] [Source ZIP]
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.