Resume

Research

Learning

Blog

Teaching

Jokes

Kernel Papers

Randomized algorithms are algorithms that have access to a source of randomness. This means that their execution path and their outputs are both random. In general, we might be interested in making statements like the following:

- \[\forall x \in \mathcal{X}, \mathbb{P}[Alg(x, r) \text{is correct}] \geq ...\]
- \[\forall x \in \mathcal{X}, \mathbb{V}[Alg(x, r) \text{'s runtime}] \leq ...\]

It turns out that there are problems for which we can find efficient and likely to be
correct *randomized* algorithms and for which we cannot find equally efficient deterministic
algorithms. There are open questions in computational complexity about what exactly randomness
buys us!

Broadly, there are 2 families of randomized algorithms:

- Las Vegas: The output is always correct, but the runtime is random
- Monte Carlo: The runtime is always fast, but the answer is possibly wrong

- Empty Pigeonholes
- Coupon Collector Problem
- Primality Testing
- Minimum Graph Cut (Kargar’s Algorithm)
- Moment Generating Functions
- Balls and Bins
- Poissonization
- Metric Embeddings
- Lovazc Local Lemma
- Algorithmic Lovazc Local Lemma
- Markov Chains
- Martingales

- Markov’s Inequality
- Chebyshev’s Inequality
- Chernoff Bounds
- Bernstein’s Inequality
- Hoeffding’s Inequality
- Azuma-Hoeffding Bound

- Mary Wootter’s Stanford CS265