Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
Nikhil Vyas, Ryan Williams · Theory of Computing Systems · 2022
Abstract 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 ( log n ) 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 function f(x1,…,xn) is sparse if it outputs 1 on O(1) values of ${\sum }_{i} x_{i}$ ∑ i x i . We show that for every sparse f, 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 be stronger than $\mathcal { C}$ C itself. In particular: # SAT algorithms for nk-size $\mathcal { C}$ C -circuits running in 2n/nk time (for all k) imply NEXP does not have $(f \circ \mathcal { C})$ ( f ∘ C ) -circuits of polynomial size. # SAT algorithms for $2^{n^{{\varepsilon }}}$ 2 n ε -size $\mathcal { C}$ C -circuits running in $2^{n-n^{{\varepsilon }}}$ 2 n − n ε time (for some ε > 0) imply Quasi-NP does 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 that Quasi-NP does not have EMA