Paper Info
Title
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits - Expanding the Reach of #SAT Algorithms.
Abstract
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this pro ram 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(1), ..., x(n)) is sparse if it outputs 1 on O(1) values of Sigma(xi)(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 circle C, which may be stronger than C itself. In particular: #SAT algorithms for n(k)-size C-circuits running in 2(n)/n(k) time (for all k) imply NEXP does not have f circle C-circuits of polynomial size. #SAT algorithms for 2(n epsilon)-size C-circuits running in 2(n-n epsilon) time (for some epsilon > 0) imply Quasi-NP does not have f circle 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 circle ACC(0) circle THR circuits of polynomial size, where EMAJ is the "exact majority" function, improving previous lower bounds against ACC(0) [Williams JACM'14] and ACC(0) circle THR [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class.
Year
DOI
Venue
2020
10.4230/LIPIcs.STACS.2020.59
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
#SAT,satisfiability,circuit complexity,exact majority,ACC
Conference
154
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Nikhil Vyas134.79
Ryan Williams2155896.40