Abstract
The Method of Conditional Expectations (sometimes also called "Method of Conditional Probabilities") is one of the prominent
derandomization techniques. Given a randomized algorithm, it allows the construction of a
deterministic algorithm with a result that matches the average-case quality of the randomized
algorithm.
Using this technique, this entry starts with a simple example, an algorithm that obtains
a cut that crosses at least half of the edges. This is a well-known approximate solution to the
Max-Cut problem. It is followed by a more complex and interesting result: an algorithm
that returns an independent set matching (or exceeding) the Caro-Wei bound: $\frac{n}{d+1}$
where $n$ is the vertex count and $d$ is the average degree of the graph.
Both algorithms are efficient and deterministic, and follow from the derandomization of a probabilistic existence proof.