Lecture Notes
(Click on one of the following courses to expand.)- Foundations of Blockchain Protocols (COMS 6998, spring 2021)
- Lecture 1: Introduction and Overview
- Lecture 2: The Dolev-Strong Protocol [very rough draft]
- Lecture 3: Simulation, Indistinguishability, and the Necessity of PKI [very rough draft]
- Lectures 4 and 5: The Asynchronous Model and the FLP Impossibility Theorem [very rough draft]
- Lecture 6: The Partially Synchronous Model, 33%, and the CAP Principle [very rough draft]
- Lecture 7: The Tendermint Protocol [very rough draft]
- Lecture 8: Longest-Chain Consensus [very rough draft]
- Lecture 9: Permissionless Consensus and Proof-of-Work [very rough draft]
- Lecture 10: Selfish Mining [incomplete and very rough draft]
- Modern Algorithmic Toolbox (with Greg Valiant) (CS168, spring 2017)
- Lecture 1: Introduction and Consistent Hashing
- Lecture 2: Approximate Heavy Hitters and the Count-Min Sketch
- Lecture 3: Similarity Metrics and kd-Trees
- Lecture 4: Dimensionality Reduction
- Lecture 5: Generalization (How Much Data Is Enough?)
- Lecture 6: Regularization
- Lecture 7: Understanding and Using Principal Component Analysis (PCA)
- Lecture 8: How PCA Works
- Lecture 9: The Singular Value Decomposition (SVD) and Low-Rank Matrix Approximations
- Lecture 10: Tensors, and Low-Rank Tensor Recovery
- Lectures 11 and 12: Spectral Graph Theory
- Lecture 13: Sampling and Estimation
- Lecture 14: Markov Chain Monte Carlo
- Lectures 15 and 16: The Fourier Transform and Convolution
- Lecture 17: Compressive Sensing
- Lecture 18: Linear and Convex Programming, with Applications to Sparse Recovery
- Lecture 19: Expander Codes
- Old notes left on the cutting room floor
- A Second Course in Algorithms (CS261, winter 2016)
- Lecture 1: Course Goals and Introduction to Maximum Flow
- Lecture 2: Augmenting Path Algorithms for Maximum Flow
- Lecture 3: The Push-Relabel Algorithm for Maximum Flow
- Lecture 4: Applications of Maximum Flows and Minimum Cuts
- Lecture 5: Minimum-Cost Bipartite Matching
- Lecture 6: Generalizations of Maximum Flow and Bipartite Matching
- Lecture 7: Linear Programming: Introduction and Applications
- Lecture 8: Linear Programming Duality (Part 1)
- Lecture 9: Linear Programming Duality (Part 2)
- Lecture 10: The Minimax Theorem and Algorithms for Linear Programming
- Lecture 11: Online Learning and the Multiplicative Weights Algorithm
- Lecture 12: Applications of Multiplicative Weights to Games and Linear Programs
- Lecture 13: Online Scheduling and Online Steiner Tree
- Lecture 14: Online Bipartite Matching
- Lecture 15: Introduction to Approximation Algorithms
- Lecture 16: The Traveling Salesman Problem
- Lecture 17: Linear Programming and Approximation Algorithms
- Lecture 18: Five Essential Tools for the Analysis of Randomized Algorithms
- Lecture 19: Beating Brute-Force Search
- Lecture 20: The Maximum Cut Problem and Semidefinite Programming
- Top 10 List
- Beyond Worst-Case Analysis (CS264, fall 2014, winter 2017)
- Full set of notes from 2014
- Lecture 1: Introduction
- Lecture 2: Instance-Optimal Geometric Algorithms
- Lecture 3: Online Paging and Resource Augmentation
- Lecture 4: Parameterized Analysis of Online Paging
- Lecture 5: Computing Independent Sets: A Parameterized Analysis (Recoverable Value)
- Lecture 6: Clustering in Approximation-Stable Instances
- Lecture 7: Perturbation Stability and Single-Link++
- Lecture 8: Exact Recovery in Stable Cut Instances
- Lecture 9: A Taste of Compressive Sensing
- Lecture 10: Planted and Semi-Random Graph Models
- Lectures 11 and 12: LP Decoding
- Lectures 12 and 13: Smoothed Simplex and Local Search (Updated 2017 version)
- Lecture 14: Smoothed Analysis of Pareto Curves
- Lecture 15: Smoothed Complexity and Pseudopolynomial-Time Algorithms
- Lecture 16: Pseudorandom Data and Universal Hashing
- Lecture 17: Self-Improving Algorithms (Updated 2017 version)
- Lecture 18: Pricing with an Unknown Distribution
- Lecture 19: Online Algorithms and Random Permutations
- Lecture 20: From Unknown Input Distributions to Instance-Optimality
- Top 10 List
- Additional new lectures in 2017
- Lecture 5: Parameterized Algorithms (new)
- Lecture 6: Perturbation-Stable Clustering (partly new)
- Lecture 8: Perturbation-Stable Maximum Cut (new)
- Lecture 9+10: Spectral Algorithms for Planted Bisection and Clique (mostly new)
- Lecture 11+12: SDP Algorithms for Semi-Random Bisection and Clique (mostly new)
- Lecture 15: Nonnegative Matrix Factorization (new)
- Lecture 16: Random Order Models (mostly new)
- Lecture 20: Application-Specific Algorithm Selection (new)
- Older notes left on the cutting-room floor
- More on instance-optimality (searching sorted lists)
- More on online paging and models of data (access graphs, Markov paging)
- More on resource augmentation (selfish routing, speed-scaling in scheduling)
- More on stable clustering (Bilu-Linial)
- More on planted models (learning mixtures of Gaussians)
- More on distributions and instance optimality (prior-free digital goods auctions)
- Full set of notes from 2014
- Incentives in Computer Science (CS269I, fall 2016)
- Lecture 1: The Draw and College Admissions
- Lecture 2: Stable Matching
- Lecture 3: Strategic Voting
- Lecture 4: Voting, Machine Learning, and Participatory Democracy
- Lecture 5: Incentives in Peer-to-Peer Networks
- Lecture 6: Incentivizing Participation
- Lecture 7: Selfish Routing and Network Over-Provisioning
- Lecture 8: Incentives in BGP Routing
- Lecture 9: Incentives in Bitcoin Mining
- Lecture 10: Incentives in Crowdsourcing
- Lecture 12: Asymmetric Information and Reputation Systems
- Lecture 13: Introduction to Auctions
- Lecture 14: First-Price and Sponsored Search Auctions
- Lecture 15: The VCG Mechanism
- Lecture 16: Revenue-Maximizing Auctions
- Lecture 17: Scoring Rules and Peer Prediction (Incentivizing Honest Forecasts and Feedback)
- Lecture 18: Prediction Markets
- Lecture 19: Time-Inconsistent Planning
- Lecture 20: Fair Division
- Algorithmic Game Theory (CS364A, fall 2013)
- The book Twenty Lectures on Algorithmic Game Theory, Cambridge University Press (2016)
- Lecture 1: Introduction and Examples
- Lecture 2: Mechanism Design Basics
- Lecture 3: Myerson's Lemma
- Lecture 4: Algorithmic Mechanism Design
- Lecture 5: Revenue-Maximizing Auctions
- Lecture 6: Simple Near-Optimal Auctions
- Lecture 7: Multi-Parameter Mechanism Design and the VCG Mechanism
- Lecture 8: Combinatorial and Wireless Spectrum Auctions
- Lecture 9: Beyond Quasi-Linearity
- Lecture 10: Kidney Exchange and Stable Matching
- Lecture 11: Selfish Routing and the Price of Anarchy
- Lecture 12: More on Selfish Routing
- Lecture 13: Potential Games and a Hierarchy of Equilibrium Concepts
- Lecture 14: Robust Price-of-Anarchy Bounds in Smooth Games
- Lecture 15: Best-Case and Strong Nash Equilibria
- Lecture 16: Best-Response Dynamics
- Lecture 17: No-Regret Dynamics
- Lecture 18: From External Regret to Swap Regret and the Minimax Theorem
- Lecture 19: Pure Nash equilibria and PLS-Completeness
- Lecture 20: Mixed Nash equilibria and PPAD-Completeness
- Top 10 List
- Frontiers in Mechanism Design (CS364B, winter 2014)
- Lecture 1: Ascending and Ex Post Incentive Compatible Mechanisms
- Lecture 2: Unit-Demand Bidders and Walrasian Equilibria
- Lecture 3: The Crawford-Knoer Auction
- Lecture 4: The Clinching Auction
- Lecture 5: The Gross Substitutes Condition
- Lecture 6: Gross Substitutes: Welfare Maximization in Polynomial Time
- Bonus Lecture: Gross Substitutes and Greedy Algorithms
- Lecture 7: Submodular Valuations
- Lecture 8: MIR and MIDR Mechanisms
- Lecture 9: MIDR Mechanisms via Scaling Algorithms
- Lecture 10: Coverage Valuations and Convex Rounding
- Lecture 11: Undominated Implementations and the Shrinking Auction
- Lecture 12: Bayesian Incentive-Compatibility
- Lecture 14: The Price of Anarchy in Simple Auctions
- Lecture 15: The Price of Anarchy of Bayes-Nash Equilibria
- Lecture 16: The Price of Anarchy First-Price Auctions
- Lecture 17: Demand Reduction in Multi-Unit Auctions Revisited
- Lecture 17.5: Beyond Smoothness and XOS Valuations
- Lecture 18: Multi-Parameter Revenue Maximization
- Lecture 19: Interim Rules and Border's Theorem
- Lecture 20: Characterization of Revenue-Maximizing Auctions
- Older notes from Fall '05 (out of date)
- Communication Complexity (for Algorithm Designers) (CS369E, winter 2015)
- Lecture 1: Data Streams: Algorithms and Lower Bounds
- Lecture 2: Lower Bounds for One-Way Communication Complexity: Disjointness, Index, and Gap-Hamming
- Lecture 3: Lower Bounds for Compressive Sensing
- Lecture 4: Boot Camp on Communication Complexity
- Lecture 5: Lower Bounds for the Extension Complexity of Polytopes
- Lecture 6: Data Structure Lower Bounds
- Lecture 7: Lower Bounds in Algorithmic Game Theory
- Lecture 8: Lower Bounds in Property Testing
- All lectures in one file
- Version for Foundations and Trends in TCS
- Miscellaneous Lecture Notes
Disclaimer: Some of these notes have been edited more than others.
Request for feedback: I always appreciate suggestions and corrections from readers.