Coupling

Polynomial Identity Testing

Karger's algorithm

Karger-Stein algorithm

Primality Testing

Markov's inequality

Chebyshev‘s inequality

Sampling-based median algorithm

Moment generating functions

Chernoff bound

Randomized routing on the hypercube

Balls and Bins

"Poissonization"

The power of 2 choices

Metric Embeddings

Bourgain's embedding

Johnson-Lindestrauss Transform

Dimension reduction and sparsity

Compressed Sensing

Restricted Isometry Property (RIP)

Ramsey's theorem

Independent Sets

De-randomization via Conditional Expectations

Second-moment method

Algorithmic Lovász local lemma

Markov Chains

Randomized algorithm for 2SAT

Fundamental Theorem of Markov Chains

Stationary distributions

Markov chain Monte Carlo (MCMC)

Mixing times

Strong stationary times

Martingales

the Doob Martingale

Azuma-Hoeffding tail bounds

The martingale stopping theorem

Pseudorandomness: expanders and extractors

CS 265 / CME 309 Randomized Algorithms and Probabilistic Analysis Stanford University Fall 2022 This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required. Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms.  CS 161 and STAT 116, or equivalents and instructor consent. 

CS 265 / CME 309 Randomized Algorithms and Probabilistic Analysis

Theoretical Computer Science

Coupling from the past

Coupling

1 courses cover this concept

CS 265 / CME 309 Randomized Algorithms and Probabilistic Analysis