2026-07-24T01:58:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11920 2024-03-06T10:49:01Z ddc:004 open_access

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms Vyas, Nikhil Williams, R. Ryan #SAT satisfiability circuit complexity exact majority ACC 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Vyas and R. Ryan Williams 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.59 urn:nbn:de:0030-drops-119200 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.59 eng https://creativecommons.org/licenses/by/3.0/legalcode