CSCI 2952U: Beyond the Worst-Case Analysis of Algorithms

Fall 2024, TuTh 2:30-3:50

Instructor: Eli Upfal (CIT 319)

Eli_Upfal@Brown.edu

A theory course/seminar for graduate and advance undergraduate students interested in the design and analysis of algorithms

Description:

The theoretical study of algorithms and data structures has focused mostly on worst-case analysis, where we prove bounds on the running time, space, approximation ratio, competitive ratio, or other measure that holds even in the worst case. More and more, however, the limitations of worst-case analysis become apparent and create new challenges. In practice, we often do not face worst-case scenarios, and the question arises of how we can tune our algorithms to work even better on the kinds of instances we are likely to see, while ideally keeping a rigorous formal framework of analysis.

In this graduate seminar course, we will review several alternatives to worst-case analysis, developed largely in the theoretical computer science literature over the past 20 years, and their most notable algorithmic applications. We will mostly study survey papers from Tim Roughgarden: “Beyond the Worst-Case Analysis of Algorithms” (Cambridge University Press, 2011).

Subjects include:

· Deterministic and Randomized Models of Data:

o Average case analysis

o Semirandom models

o Sparse recovery

o Perturbation resistance

o Self-improving algorithms

· Smoothed Analysis

· Competitive analysis

· Application to Machine Learning:

o Noisy data

o Robust high dimensional statistics

o Why do local models solve nonconvex problems?

o Generalization in Overparameterized models

o Instant optimality in testing and learning

· Data Driven Algorithm Design

· Algorithms with Predictions

· Distribution-Free Models for Social Networks