Overview
Randomness is a surprisingly powerful resource in modern computation, enabling algorithms that are dramatically simpler and faster than their deterministic counterparts. This course is a journey through several areas of theoretical computer science in which randomization has proved immensely successful, highlighting the core techniques that underlie the design and analysis of randomized algorithms. We will also explore their inherent limitations through tools such as query complexity and communication complexity.
Prerequisite background: A strong background in undergraduate algorithms. The material is largely complementary to Prof. Anupam Gupta’s Fall 2025 course on Randomized Algorithms.
Topics
Topics covered include:
- Sublinear Algorithms
- Query and Communication Complexity (limits of sublinear algorithms)
- Approximation algorithms via Randomized Rounding
- Algebraic fingerprinting and Polynomial Identity Testing
- Interactive proofs, PCP theorem, and Hardness of Approximation
- Random Walks and Markov chains
Lecture schedule
-
Lecture 1:
Course overview; randomization in action: matrix multiplication verification, equality testing, and global mincut.
-
Lecture 2:
Randomized complexity classes and relationships among them.
-
Lecture 3:
Tail inequalities and their applications.
-
Lectures 4–7:
An introduction to sublinear algorithms, and exploration of limits of sublinear computation via
query complexity and communication complexity.
Course Materials
- Course materials: All lecture notes and homeworks are available on NYU Brightspace.