Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-114 | 18th July 2015 14:12

#### #SAT Algorithms from Shrinkage

TR15-114
Authors: Avishay Tal
Publication: 18th July 2015 14:44
We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et al. (CCC, 2014). Our result uses the tight shrinkage in expectation'' result of de Morgan formulas by Håstad (SICOMP, 1998) as a black-box, and improves upon the result of Chen et al. (MFCS, 2014) that gave deterministic counting algorithms for de Morgan formulas of size at most $n^{2.63}$.
Our algorithm generalizes to other bases of Boolean gates giving a $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$ time counting algorithm for formulas of size at most $n^{\Gamma +1 - O(\epsilon)}$, where $\Gamma$ is the shrinkage exponent for formulas using gates from the basis.