CS294-134 — Beyond Worst-Case Analysis — Fall 2017
[lecture notes] [exams and projects]
Trevisan, 625 Soda Hall, email luca at berkeley dot edu
Classes are TuTh, 3:30-5pm, in 310 Soda
Office hours: TBA
About the course
Worst-case analysis sometimes overestimates the difficulty of certain problems in practice.
In this course we will review more refined methods for the analysis of algorithms, including average-case analysis for random instances, analysis of distributions with a "planted" solution, semi-random models which combine random and adversarial choices, and machine learning problems in which the input is a collection of iid samples from an arbitrary unknown distribution.
We will conclude with a brief overview of the theory of average-case complexity, and the evidence that we have that certain problems remain hard even when analyzed with respect to natural classes of distributions.
Here is a tentative list of topics that we will cover:
- Properties of random graphs
- Cliques in random graphs
- Independent sets in random graphs
- Planted bisection and the stochastic block model
- Recovering a planted sparse vector in a random subspace
- Matrix completion
- Finding cuts in semi-random graph models
- Stable cuts and stable clustering
- Compressed sensing, LP decoding, and sparse FFT
- Smoothed analysis of the simplex
- Randomized hashing of worst-case data vs deterministic hashing of random data
- An introduction to average-case complexity
Prerequisites: CS170 or equivalent, a good understanding of discrete probability.
Assignments: scribing one lecture, a take-home midterm exam, a final project.
The main reference will be a set of lecture notes. Our course will have a large overlap with this course, for which videos and lecture notes are available.
Exams and Projects