Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms. We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in textQuasiNP  textNTIMEn(log n)O(1) and textNEXP do not have small circuits from various circuit classes cal C, by showing that cal C admits nontrivial satisfiability andor SAT algorithms which beat exhaustive search by a minor amount.  this :62,paper, we present a new strong lower bound consequence of nontrivial SAT algorithm for a circuit class mathcal C. Say a symmetric Boolean function f(x_1,ldots,x_n) is sparse if it outputs 1 on O(1) values of sum_i x_i. We show that for every sparse f, and for all typical cal C, faster SAT algorithms for cal C circuits actually imply lower bounds against the circuit class f circ cal C, which may be stronger than cal C itself. In particular:  algorithms for :143,168,nksize cal Ccircuits running in 2nnk time (for all k) imply textNEXP does not have f circ cal Ccircuits of polynomial size.  algorithms for 2nepsilonsize cal Ccircuits running in 2nnepsilon time (for some epsilon u003e 0) imply textQuasiNP does not have f circ cal Ccircuits of polynomial size.  SAT algorithms from the :195,literature, one immediate corollary of our results is that textQuasiNP does not have textEMAJ circ textACC0 circ textTHR circuits of polynomial size, where textEMAJ is the exact majority function, improving previous lower bounds against textACC0 Williams JACMu002714 and textACC0 circ textTHR Williams STOCu002714, MurrayWilliams STOCu002718. This is the first nontrivial lower bound against such a circuit class.

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits We show that any nvariate polynomial computable by a syntactically multilinear circuit of size operatornamepoly(n) can be computed by a depth4 syntactically multilinear (SigmaPiSigmaPi) circuit of size at most expleft(Oleft(sqrtnlog nright)right). For degree d  omega(nlog n), this improves upon the upper bound of expleft(O(sqrtdlog n)right) obtained by TavenasciteT15 for general circuits, and is known to be asymptotically optimal in the exponent when d u003c nepsilon for a small enough constant epsilon. Our upper bound matches the lower bound of expleft(Omegaleft(sqrtnlog nright)right) proved by Raz and YehudayoffciteRY09, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.  :111,generally, we show that an nvariate polynomial computable by a syntactically multilinear circuit of size operatornamepoly(n) can be computed by a syntactically multilinear circuit of productdepth Delta of size at most expleft(Oleft(Delta cdot (nlog n)1Delta cdot log nright)right). It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to oleft(left(nlog nright)1Deltacdot log nright).