Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-114 | 18th July 2015 14:12

#SAT Algorithms from Shrinkage


Authors: Avishay Tal
Publication: 18th July 2015 14:44
Downloads: 1784


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.

ISSN 1433-8092 | Imprint