2014/01/10 by Williams, Ryan
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1401.2444
Let ACC ∘ THR be the class of constant-depth circuits comprised of AND, OR, and MODm 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^no(1) ACC ∘ THR circuits of size 2^no(1), on all possible inputs, in 2n ⋅ poly(n) time. Several consequences are derived: \bullet The number of satisfying assignments to an ACC ∘ THR circuit of subexponential size can be computed in 2^n-nε time (where ε > 0 depends on the depth and modulus of the circuit). \bullet NEXP does not have quasi-polynomial size ACC ∘ THR circuits, nor does NEXP have quasi-polynomial size ACC ∘ SYM circuits. Nontrivial size lower bounds were not known even for AND ∘ OR ∘ THR circuits. \bullet Every 0-1 integer linear program with n Boolean variables and s linear constraints is solvable in 2^n-Ω(n/((log M)(log s)5))⋅ 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 [-2poly(n),2poly(n)] and poly(n) constraints can be solved in 2n-Ω(n/log6 n) time.) We also present an algorithm for evaluating depth-two linear threshold circuits (a.k.a., THR ∘ THR) with exponential weights and 2n/24 size on all 2n input assignments, running in 2n ⋅ poly(n) time. This is evidence that non-uniform lower bounds for THR ∘ THR are within reach.