文章基本信息

标题：Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
本地全文：下载
作者：Nikhil Vyas ; R. Ryan Williams
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：59:1-59:17
DOI：10.4230/LIPIcs.STACS.2020.59
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Quasi-NP = NTIME[n^{(log n)^O(1)}] and NEXP do not have small circuits (in the worst case and/or on average) from various circuit classes C, by showing that 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 {C}. Say a symmetric Boolean function f(xâ,,â¦,x_n) is sparse if it outputs 1 on O(1) values of â^'_i x_i. We show that for every sparse f, and for all "typical" C, faster #SAT algorithms for C circuits actually imply lower bounds against the circuit class f â^~ C, which may be stronger than C itself. In particular: - #SAT algorithms for n^k-size C-circuits running in 2â¿/n^k time (for all k) imply NEXP does not have f â^~ C-circuits of polynomial size. - #SAT algorithms for 2^{n^Îµ}-size C-circuits running in 2^{n-n^Îµ} time (for some Îµ > 0) imply Quasi-NP does not have 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 EMAJ â^~ ACCâ° â^~ THR circuits of polynomial size, where EMAJ is the "exact majority" function, improving previous lower bounds against ACCâ° [Williams JACM'14] and ACCâ° â^~ THR [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class.
关键词：#SAT; satisfiability; circuit complexity; exact majority; ACC