Variance of MAXSAT clause satisfiability
Suppose that the MAXSAT instance consists of clauses $C_1,\ldots,C_m$. Denote by $X$ the expected number of clauses satisfied by a random assignment. Then
$$
\mathbb{E}\left[\binom{X}{d}\right] = \sum_{\substack{S \subseteq [m] \\ |S|=d}} \Pr[C_i \text{ is satisfied for all } i \in S].
$$
This gives a roughly $O(m^d)$ algorithm for computing the $d$th moment.