Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.

DOI10.4230/LIPIcs.STACS.2020.59OpenAlexW3013163752MaRDI QIDQ5874336

Nikhil Vyas, R. Ryan Williams

Publication date: 7 February 2023

Full work available at URL: https://arxiv.org/abs/2001.07788

zbMATH Keywords

satisfiabilitycircuit complexityACC\#SATexact majority

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Weights of exact threshold functions ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Average-case rigidity lower bounds

This page was built for publication: Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.