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.