Derandomization with Conditional Expectations

Emin Karayel 📧

March 24, 2024

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.


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.


BSD License


Session Derandomization_Conditional_Expectations