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

### License

BSD License

### Topics

- Computer science/Algorithms/Randomized
- Computer science/Algorithms/Graph

### Session Derandomization_Conditional_Expectations

- Derandomization_Conditional_Expectations_Preliminary
- Derandomization_Conditional_Expectations_Cut
- Derandomization_Conditional_Expectations_Independent_Set

### Depends on

- Distributed Distinct Elements
- Undirected Graph Theory

## Cite

×

Derandomization_Conditional_Expectations-AFP

    @article{Derandomization_Conditional_Expectations-AFP,
      author  = {Emin Karayel},
      title   = {Derandomization with Conditional Expectations},
      journal = {Archive of Formal Proofs},
      month   = {March},
      year    = {2024},
      note    = {\url{https://isa-afp.org/entries/Derandomization_Conditional_Expectations.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest