A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.
Balaji, Swapnam, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan · IT University Of Copenhagen (IT University of Copenhagen) · 2022
We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.