ECCC-Report TR18-162https://eccc.weizmann.ac.il/report/2018/162Comments and Revisions published for TR18-162en-usSun, 16 Sep 2018 14:43:58 +0300
Paper TR18-162
| A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates |
Swapnam Bajpai,
Vaibhav Krishan,
Deepanshu Kush,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2018/162We 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.
Formally, for any constants $d,k$, there is an $\epsilon > 0$ such that the algorithm counts the number of satisfying assignments to a given depth-$d$ circuit $C$ made up of $k$-PTF gates such that $C$ has size at most $n^{1+\epsilon}$. The algorithm runs in time $2^{n-n^{\Omega(\epsilon)}}$.
Before our result, no algorithm for beating brute-force search was known even for a single degree-$2$ PTF (which is a depth-$1$ circuit of linear size).
The main new tool is the use of a learning algorithm for learning degree-$1$ PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into a memoization approach that yields the #SAT algorithms.Sun, 16 Sep 2018 14:43:58 +0300https://eccc.weizmann.ac.il/report/2018/162