NYU Randomized Algorithms

Instructor: Anupam Gupta

Lectures: Thursdays at 2:45-4:45pm ET, 312 Warren Weaver

Professors office hours: By appointment.

Overview: This is a graduate course in randomized algorithms, where we cover how randomness can often lead to simple, improved algorithms (using less time and space). We will cover topics that go beyond the Honors Algorithms course. Specifically, we will see how basic facts about means and standard deviations (i.e., the first and second moments) can already give new algorithms. We will then show how to use concentration (aka Chernoff-Hoeffding) bounds, the Lovasz Local Lemma, Random walks on Graphs, and other probabilistic tools useful for algorithm design. Time permitting, we will discuss derandomization.

The goal will be to discuss both general techniques and specific algorithms: we will see algorithms for finding min-cuts and to sparsify graphs, finding satisfying assignments to Boolean formulas, counting the number of distinct elements in a data stream with very little space, assigning jobs to machines or routing paths in graphs to minimize load, sampling random matchings, approximating metric spaces by trees, reducing the dimension of data, learning hypothesis from samples of data, and other topics. A detailed syllabus will be posted as the course progresses.

Prerequisites: We expect students to have a good background in algorithm design. For example, Honors Analysis of Algorithms (CSCI-GA.3520-001), Algorithms 2 (CS-GY 6043), Algorithmic Machine Learning and Data Science (CS-GY 6763), or similar graduate-level Algorithms courses. SOlid understanding of probability; we will use some linear algebra and calculus, and mathematical maturity is a must.

Grading breakdown: The course evaluation will be based on 4-5 homework sets, and a research project/presentation at the end of the course. Depending on the class size, some of the homeworks may be oral homeworks(!).

Course Infrastructure: We will use Ed for course discussions, Gradescope for homework submissions, and Brightspace for all course material.

Collaboration: For some of the problems, we will ask you to work solo, whereas for others we will allow collaboration in small groups. Each person must write their own solutions to submit.

Resources: There is no official textbook for the course. We like these books:
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
Probability and Computing by Michael Mitzenmacher and Eli Upfal
The Probabilistic Method by Noga Alon and Joel Spencer.
We will post readings from books and research papers, which will be available free online or via the NYU library.

Homeworks: