CS3936: Topic in Modern Algorithms (Fall 2025)

Introduction

This semester, the course will focus on high-dimensional probability. A more friendly name might be algorithms for big data. I will mainly focus on concentration inequalities and suprema of random variables.

Course Information

• Location: 致远书院（光彪楼） 203
• Time: 12:55 - 15:40, every Monday
• Instructor: Chihao Zhang
• TA: Yuchen He

References

[Ver18] High-Dimensional Probability, Roman Vershynin, Cambridge University Press.

[Van16] Probability in High Dimension, Ramon van Handel.

[Roc20] Modern Discrete Probability - An Essential Toolkit, Sebastien Roch, Cambridge University Press.

Outline

• Lecture 11: Supremum of random variables, Covering and Packing
• Lecture 10: Pathwise Method, Johnson-Lindenstrauss Lemma
• Lecture 9: Tensorization of Entropy, the Modified Log-Sobolev inequality
• Lecture 8: Tensorization of Variance, the Poincaré inequality
• Lecture 7: Markov Semigroup, Langevin Dynamics and DDPMs
• Lecture 6: Diffusions and Itô Calculus
• Lecture 5: Geometry View of Markov Chains, Brownian motion
• Lecture 4: Discrete Markov Chains
• Lecture 3: Concentration Inequalities via Martingale
• Lecture 2: Sub-Gaussian and Sub-Exponential Random Variables
• Lecture 1: Basic Concentration Inequalities