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

### 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.