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: Wednesdays 2-3pm, 625 Soda Hall (Starting August 30)

Piazza: piazza.com/berkeley/fall2017/cs294134

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.


  1. 8/24. Introduction, clique in random graphs.
  2. 8/29. Max Cut in random graphs, Independent set in sparse random graphs.
    [summary] [notes]
  3. 8/31. Independent set and Max Cut in sparse random graphs.
    [summary] [notes]
  4. 9/5. Semidefinite programming and the SDP relaxation of Max Cut.
    [summary] [notes]
  5. 9/7. Optimal bounds for Max Cut in random graphs using the SDP relaxation.
    [summary] [notes]
  6. 9/12. Understanding the spectrum of the adjacency matrix of a random graph.
    [see section 5 and 6 in these notes] [summary] [notes]
  7. 9/14. Finding planted cliques in random graphs. Introduction to random k-SAT.
    [See this paper for the planted clique algorithms]
  8. 9/19. More about certifying the unsatisfiability of random k-SAT.
    [this is the paper introducing the reduction from certifying unsatisfiability of random k-SAT to certifying upper bounds to independent set in random graphs]
    [this is the Feige-Ofek paper on spectral properties of random graphs with constant average degree]
    [notes (updated 9/27)]
  9. 9/21. Introducing the stochastic block model.
  10. 9/26. Matrix norms other than the spectral norm, and Grothendieck's inequality.
  11. 9/28. Approximate reconstruction in the stochastic block model
    See also this paper
  12. 10/3. Exact reconstruction in the stochastic block model
    See this paper and these notes [notes in preparation]
  13. 10/5. Exact reconstruction in the stochastic block model, continued
    [notes in preparation]
  14. 10/10. Exact reconstruction in the stochastic block model, conclusion. Semi-random models for cut problems
    [notes in preparation]
  15. 10/12. Notions of "stability" for cut and clustering problem. Certifying that a random linear subspace has no sparse vector.
    The first part of the lecture referenced: The second part of the lecture was about Section 2.1 of this paper by Demanet and Hand

  16. 10/17. Finding a planted sparse vector in a random subspace using linear programming.
Plan for remaining lectures (subject to change)

Exams and Projects