Name
Abstract | ||
|---|---|---|
We show that there is a better-than-brute-force 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
$$\varepsilon > 0$$
such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-d circuit C made up of k-PTF gates such that C has at most
$$n^{1+\varepsilon }$$
many wires. The algorithm runs in time
$$2^{n-n^{\Omega (\varepsilon )}}.$$
Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-k PTF (which is a depth-1 circuit with linearly many wires).We give two different algorithms for the case of a single PTF. The first uses a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett and Moran (STOC 2018), and the second uses a proof of Hofmeister (COCOON 1996) for converting a degree-1 PTF to a depth-two threshold circuit with small weights. We show that both these ideas fit nicely into a memoization approach that yields the #SAT algorithms. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-021-00915-7 | Algorithmica |
DocType | Volume | Issue |
Journal | 84 | 4 |
ISSN | Citations | PageRank |
0178-4617 | 0 | 0.34 |
References | Authors | |
11 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swapnam Bajpai | 1 | 0 | 0.34 |
| Vaibhav Krishan | 2 | 0 | 0.34 |
| Deepanshu Kush | 3 | 0 | 1.35 |
| Nutan Limaye | 4 | 134 | 20.59 |
| Srikanth Srinivasan | 5 | 2 | 3.75 |