CS 7870: Seminar in Theoretical Computer Science; Fall 2023

Syllabus Tentative Course Schedule

A Modern Toolkit for Algorithms and Analysis

Instructor: Rajmohan Rajaraman

Description Textbook Grading Policies Recitations

Lectures: TF 09:50-11:30, HS 107

Office Hours: F 2:00-3:00 PM; M 5:00-6:00 PM, 240 WVH

Course Description

This course covers selections from a modern toolkit for algorithmic design and analysis. The worst-case analysis of algorithms has formed the foundation for algorithm design and complexity theory. The natural notions of reductions and completeness have allowed us to categorize problems effectively according to their hardness as well as solve a wide range of problems by relating them to one another. Illustrating these successes, the course will include classic algorithmic techniques including linear programming, greedy algorithms, and local search, and established analysis frameworks including approximation algorithms, competitive analysis, and regret bounds.

Many algorithmic problems faced in modern machine learning and data science applications are known to be intractable in the worst case. Yet, under many practical scenarios, they appear to be tractable. Over the past decade, alternative "beyond worst-case models" have been introduced to explain practical tractability as well as develop improved algorithms for these hard problems. A major part of the course will explore the foundations of data science via the lens of beyond worst-case analysis. The underlying domain is vast, so the course will only offer a glimpse of the problems, models, and results in this space.

Here is the set of topics we plan to cover in the course.

Clustering: k-median, k-center, perturbation stability
Linear programming: Introduction and applications, geometry, duality
High-dimensional space: Basic probability, geometry of high dimensions, random projection, Principal Component Analysis, compressed sensing
Smoothed analysis: Simplex algorithm for linear programming; local search
Optimization in Machine learning: Gradient descent, stochastic gradient descent, online convex optimization
Online algorithms: multiplicative weights method, competitive analysis, algorithms with ML predictions

Readings

The readings for the course will be drawn from classic articles, recent papers, lecture notes due to leading researchers in the area, and chapters from the following books. Readings for individual lectures will be included in the schedule. We will prepare notes for every lecture, and most of the relevant material is available online.

Beyond the Worst-Case Analysis of Algorithms, edited by Tim Roughgarden, Cambridge University Press, 2020.

Foundations of Data Science, by Avrim Blum, John Hopcroft, and Ravindran Kannan, Cambridge University Press, 2020.

The Design of Approximation Algorithms, by David Williamson and David Shmoys, Cambridge University Press, 2010.

Lecture notes due to Tim Roughgarden, Elad Hazan

Grading

This is a seminar and there will be no stress-inducing components such as quizzes and exams. Grades will be based on 3 problem sets (30%), two lecture note scribes (20%), and a research or survey project, consisting of a mid-term proposal (10%), a final report (20%), and a final presentation (20%).