CS3936: Topics in Modern Algorithms (Fall 2026)
Course Design
In the age of AI, we should explore more efficient ways to learn theoretical computer science. This semester, I have designed the course in a Gems of TCS format covering several central topics across modern algorithm design and analysis. Each chapter of the lecture notes is organized into three layers:
- Course Content: In class, we focus on classic, foundational examples and core proof ideas to build first-principles intuition and a shared mathematical toolkit.
- Reading Contents & Further Topics: Deeper technical derivations, extended applications, and pointers to active research directions are placed in Reading Contents and Further Topics for open-ended exploration outside the classroom.
All coursework and assessments revolve around Reading Contents and Further Topics. Building on the foundations developed in class, a key component of the course—and of the final evaluation—is to use modern AI tools to digest, critically verify, and even improve upon frontier research papers.
Lecture Notes (in English)
- Chapter 1: Concentration Inequalities and Randomized Algorithms
- Chapter 2: Sampling and Markov Chains: Coupling, Spectrum, and Cheeger’s Inequality
- Chapter 3: Fourier Analysis of Boolean Functions: Arrow’s Theorem and the Power of Small Coalitions
- Chapter 4: Online Learning, Regularization, and Optimization