#
CS294-134 — Beyond Worst-Case Analysis — Fall 2017

**[general info] **
**[lecture notes] [exams and projects]**

## What's new

## general information

**Instructor**: Luca
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.

### References

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.

### Lectures

### Exams and Projects