ECCC-Report TR15-114https://eccc.weizmann.ac.il/report/2015/114Comments and Revisions published for TR15-114en-usSat, 18 Jul 2015 14:44:16 +0300
Paper TR15-114
| #SAT Algorithms from Shrinkage |
Avishay Tal
https://eccc.weizmann.ac.il/report/2015/114We 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.Sat, 18 Jul 2015 14:44:16 +0300https://eccc.weizmann.ac.il/report/2015/114