论文标题
针对ACC电路的稀疏对称功能的下限：扩展$ \＃$ SAT算法的覆盖范围
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms
论文作者
论文摘要
我们继续通过电路满足算法来证明电路下限的程序。到目前为止，该程序已经产生了几个具体的结果，证明了$ \ text {quasi-np} = \ text {ntime} [n^{（\ log n）^{o（1）}] $ and $ \ text {nexp} $没有从各种电路clast $ cal cal cal cal cal cal cal，非平凡的满意度和/或$ \＃$ SAT算法，这些算法以少量数量击败了详尽的搜索。 在本文中，我们提出了针对电路类$ {\ Mathcal C} $的非平凡$ \＃$ sat算法的新的强大下限结果。假设对称的布尔函数$ f（x_1，\ ldots，x_n）$如果在$ o（1）$值上输出$ 1 $的$ \ sum_i x_i $，则很少。我们表明，对于每个稀疏$ f $，对于所有“典型” $ {\ cal c} $，更快的$ \＃$ $ $ sat Algorithms for $ {\ cal c} $电路实际上意味着对电路类别$ f \ circ f \ circ {\ cal c} $的下降范围，这可能比$ {\ cal cal cal cal cal cal and ofter。尤其： $ n^k $ -size $ {\ cal c} $ - 以$ 2^n/n^k $ time（所有$ k $）表示$ \ text {nexp} $没有$ f \ f \ f \ f \ f \ circe {\ cal c c} $ - circuitits $ n^k $ - size $ {\ cal c} $ - $ n^k $ - size $ {nexp} $没有$ n^k $ - $ 2^{n^ε} $ - 尺寸$ {\ cal c} $ - 以$ 2^{n-n-n^ε} $ time（对于某些$ε> 0 $）暗示$ \ text {quasi-np} $没有$ f \ circial occiate of cicdiT， 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与$ \ text {acc}^0 $ [Williams jacm'14]和$ \ text {acc}^0 \ circ \ text {thr} $ [Williams stoc'14]，[Murray-Williams stoc'18]界限。这是针对这种电路类别的第一个非平凡的下限。
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^ε}$-size ${\cal C}$-circuits running in $2^{n-n^ε}$ time (for some $ε> 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.
