Derandomization with Conditional Expectations (Q7361332)

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.