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:

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