How does derandomization of 3SAT work via conditional expectations?

Question

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8

• But I do not understand how from the above argument it follows that given a $m$ clause SAT instance the probability of satisfying at least $7/8 - 1/2m$ fraction of the clauses is at least $1/poly(m)$ ?

[..firstly even in a single clause case its not clear how the 7/8 result can hold if variables are repeated - and in the multi-clause case there will now be correlations across clauses - and hence its hardly clear to me as to what is happening!..]

I believe there is some sort of a Markov inequality going on but I can't see it.

• Now apparently one can derandomize this using "conditional expectation". (vaguely I understand that it is some way of estimating what is the chance of satisfying the formula when randomizing over a subset of the variables while keeping the others' values fixed and then probably changing the subset in every round) This is totally unfamiliar to me as to how the above probabilistic argument can be converted into a deterministic one so as to ensure finding of an assignment of values to variables such that always at least 7/8 of the clauses are satisfied.

[..apparently the above can also be thought via "3-wise independent sample space" - if someone can help understand that then that would be great!..]

Answer 1

If you choose an assignment at random, each particular clause is satisfied with probability $7/8$. Using linearity of expectation, this shows that if you choose an assignment at random, then the number of satisfied clauses is at least $(7/8)n$. The idea is to have an indicator variable $X_i$ for clause $i$, which states that the clause is satisfied. Since $\mathbb{E}[X_i] = \Pr[X_i] = 7/8$, by linearity of expectation we have $\mathbb{E}[\sum_{i=1}^m X_i] = (7/8)m$. In particular, some assignment satisfies at least $(7/8)m$ clauses.

Let now $X$ be the number of unsatisfied clauses under a random assignment. Then $\mathbb{E}[X] = (1/8)m$, and so Markov's inequality shows that $$ \Pr[X \geq (C/8)m] \leq 1/C. $$ By choosing an appropriate $C$ you get your first bullet (try it out!).

Regarding the method of conditional expectations, there are many online resources, for example this one (the first hit on a popular search engine). There are many others.

Finally, if $\mathcal{D}$ is a 3-wise independent sample space – this just means that if $(v_1,\ldots,v_n) \sim \mathcal{D}$, then for any $i<j<k$, the joint distribution of $(v_i,v_j,v_k)$ is uniform over all eight possibilities – then it is still the case that each clause is satisfied with probability exactly $7/8$ (why?). Therefore if we choose a random assignment according to $\mathcal{D}$, the expected number of satisfied assignments is exactly $(7/8)m$. In particular, some assignment in the support of $\mathcal{D}$ – that is, an assignment which is generated by $\mathcal{D}$ with some probability – satisfies at least $(7/8)m$ clauses.

Why is this helpful? There are 3-wise independent samples spaces of polynomial size. We can derandomize the random 3SAT algorithm by taking such a sample space and trying out all assignments in its support. One of them will satisfy at least $(7/8)m$ clauses.