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!..]