# CS 7870: Seminar in Theoretical Computer Science; Fall 2023

### A Modern Toolkit for Algorithms and Analysis

#### 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%).