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 in time 2 n − n pol y ( n ) , for any small constant 0"> 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 pol y ( n ) time counting algorithm for formulas of size at most n +1 − O ( ) , where is the shrinkage exponent for formulas using gates from the basis.