  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 $\text{Quasi-NP} = \text{NTIME}[n^{(\log
n)^{O(1)}}]$ and $\text{NEXP}$ do not have small circuits from various circuit
classes ${\cal C}$, by showing that ${\cal 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 non-trivial
$\#$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:
  $\#$SAT algorithms for $n^k$-size ${\cal C}$-circuits running in $2^n/n^k$
time (for all $k$) imply $\text{NEXP}$ does not have $f \circ {\cal
C}$-circuits of polynomial size.
  $\#$SAT algorithms for $2^{n^{\epsilon}}$-size ${\cal C}$-circuits running in
$2^{n-n^{\epsilon}}$ time (for some $\epsilon > 0$) imply $\text{Quasi-NP}$
does not have $f \circ {\cal C}$-circuits of polynomial size.
  Applying $\#$SAT algorithms from the literature, one immediate corollary of
our results is that $\text{Quasi-NP}$ does not have $\text{EMAJ} \circ
\text{ACC}^0 \circ \text{THR}$ circuits of polynomial size, where $\text{EMAJ}$
is the "exact majority" function, improving previous lower bounds against
$\text{ACC}^0$ [Williams JACM'14] and $\text{ACC}^0 \circ \text{THR}$ [Williams
STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound
against such a circuit class.
