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 $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$Quasi-NP=NTIME[n(logn)O(1)] and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes $\mathcal { C}$C , by showing that $\mathcal { C}$C admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class ${\mathcal C}$C . Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of ${\sum }_{i} x_{i}$∑ixi . We show that for every sparsef, and for all “typical” $\mathcal { C}$C , faster#SAT algorithms for $\mathcal { C}$C circuits imply lower bounds against the circuit class $f \circ \mathcal { C}$f∘C , which may bestrongerthan $\mathcal { C}$C itself. In particular: #SAT algorithms forn^k-size $\mathcal { C}$C -circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have $(f \circ \mathcal { C})$(f∘C) -circuits of polynomial size. #SAT algorithms for $2^{n^{{\varepsilon }}}$2nε -size $\mathcal { C}$C -circuits running in $2^{n-n^{{\varepsilon }}}$2n−nε time (for someε> 0) implyQuasi-NPdoes not have $(f \circ \mathcal { C})$(f∘C) -circuits of polynomial size. Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.