License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.59
URN: urn:nbn:de:0030-drops-119200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11920/
Vyas, Nikhil ;
Williams, R. Ryan
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 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.
BibTeX - Entry
@InProceedings{vyas_et_al:LIPIcs:2020:11920,
author = {Nikhil Vyas and R. Ryan Williams},
title = {{Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {59:1--59:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11920},
URN = {urn:nbn:de:0030-drops-119200},
doi = {10.4230/LIPIcs.STACS.2020.59},
annote = {Keywords: #SAT, satisfiability, circuit complexity, exact majority, ACC}
}
|
Keywords: |
|
#SAT, satisfiability, circuit complexity, exact majority, ACC |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
