Theory of Computing
-------------------
Title : New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates
Authors : R. Ryan Williams
Volume : 14
Number : 17
Pages : 1-25
URL : http://www.theoryofcomputing.org/articles/v014a017
Abstract
--------
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
$AND \circ 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.