All reports by Author Vaibhav Krishan:

__
TR18-162
| 16th September 2018
__

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

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 ... more >>>