# Variance of MAXSAT clause satisfiability

For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.

Is it likewise possible to compute the variance of the number of clauses satisfied? And I mean an exact computation, not an estimate.

In general, which moments are easy to compute, and which are hard?

I would prefer an answer for general MAXSAT but would also be interested in the special case of MAX-3-SAT.

• All constant moments, at the very least, should be easy to compute. It’s an exercise. – Yuval Filmus Nov 14 '18 at 1:07
• What do you mean by "constant" moments? – Mike Battaglia Nov 14 '18 at 1:14
• I accidentally assumed that the MAXSAT instance is also chosen at random. When the instance is fixed and has size $m$, then you should be able to compute $\mathbb{E}[\binom{X}{d}]$, where $X$ is the number of satisfied clauses under a random assignment, in time $O(m^d)$. It's still an exercise. – Yuval Filmus Nov 14 '18 at 1:19

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.