Topics in theoretical computer science

This year's course will explore the power of randomness in algorithm design, highlighting how probabilistic techniques can lead to elegant and efficient solutions to a wide range of computational problems. We will cover both foundational methods and advanced applications, with topics drawn from graph algorithms, data structures, learning, and more. The goal is to introduce core probabilistic tools through concrete algorithmic applications. Topics may include: algorithms for finding min-cuts (including isolating cuts and near-linear time methods), graph sparsification (e.g., Karger's and Benczur-Karger techniques), balls-and-bins processes and the power of two choices, low-distortion embeddings and dimension reduction, randomized rounding and discrepancy minimization, fast randomized algorithms for approximate counting via Markov chains, learning from samples, differential privacy, and randomized methods in geometry and communication complexity. We will also discuss fundamental tools such as the Chernoff bound, the Lovasz Local Lemma, martingale inequalities, limited independence, and coupling methods. Selected topics such as online learning, bandits, planted and semi-random models, and randomized primality testing may be included depending on time and interest.

We are running this course in collaboration and in parallel with the Randomized Algorithms course at NYU, taught by Professor Anupam Gupta.

Introduction, Min-Cuts in Graphs via Randomization: Contractions and Isolating Cuts

First and Second Moment Methods, Random Graphs, and Concentration of Measure

Chernoff-Hoeffding Concentration Bounds and Applications

Application of concentration inequalities: graph sparsification, power of two choices

Lovasz Local Lemma

Random Walks