New algorithms and lower bounds for circuits with linear threshold gates

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: $\bullet$ The number of satisfying assignments to an $ACC\circ THR$ circuit of subexponential size can be computed in $2^{n-n^{\epsilon }}$ time (where $\epsilon >0$ depends on the depth and modulus of the circuit). $\bullet$ $NEXP$ does not have quasi-polynomial size $ACC\circ THR$ circuits, nor does $NEXP$ have quasi-polynomial size $ACC\circ SYM$ circuits. Nontrivial size lower bounds were not known even for $AND\circ OR\circ THR$ circuits. $\bullet$ Every 0-1 integer linear program with $n$ Boolean variables and $s$ linear constraints is solvable in $2^{n-\Omega (n/((\log M)(\log s{)}^5))}\cdot poly(s,n,M)$ time with high probability, where $M$ upper bounds the bit complexity of the coefficients. (For example, 0-1 integer programs with weights in $[-2^{poly(n)},2^{poly(n)}]$ and $poly(n)$ constraints can be solved in $2^{n-\Omega (n/{\log }^{6}n)}$ time.) We also present an algorithm for evaluating depth-two linear threshold circuits (a.k.a., $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.

References in corpus (2)

• Algorithms versus Circuit Lower Bounds
• Faster all-pairs shortest paths via circuit complexity

Cited by in corpus (5)

• On Polynomial Approximations to ${AC}^0$
• Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
• Faster all-pairs shortest paths via circuit complexity
• Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems