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