Beyond Worst-Case Analysis | Computational Problems | Algorithmic Guarantees

Explore alternatives to traditional worst-case analysis and their applications in various computational domains, including online algorithms, machine learning, and more.

Introduction

This course has two intertwined goals. The first goal is to survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited, because it fails to differentiate meaningfully between different solutions, recommends an empirically "wrong" solution over the "right" one, or gives excessively pessimistic performance predictions. The second goal is to study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance.

Highlights

• Covers instance optimality, smoothed analysis, parameterized analysis and condition numbers, models of data, average-case analysis, robust distributional analysis, resource augmentation, and planted and semi-random graph models
• Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, scheduling, linear programming, hashing, and auction theory
• Includes weekly exercise sets and optional paper-reading project

Recommendation

This course is recommended for students with a background in undergraduate algorithms (CS161 or equivalent) who are interested in exploring alternatives to traditional worst-case analysis and their applications in various computational domains.