Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-162 | 16th September 2018 09:08

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates


Authors: Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
Publication: 16th September 2018 14:43
Downloads: 766


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.

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.

ISSN 1433-8092 | Imprint