Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
From MaRDI portal
Publication:2701071
DOI10.1007/s00224-022-10106-8OpenAlexW3001571187MaRDI QIDQ2701071
Publication date: 27 April 2023
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-022-10106-8
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of combinatorial problems with succinct input representation
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- PP is closed under intersection
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- A Sample of Samplers: A Computational Perspective on Sampling
- Linear-time encodable and decodable error-correcting codes
- Nonuniform ACC Circuit Lower Bounds
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
- Interactive proofs and the hardness of approximating cliques
- New algorithms and lower bounds for circuits with linear threshold gates
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Strong average-case lower bounds from non-trivial derandomization
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Computational Complexity
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
