CS 294. Efficient Algorithms and Computational Complexity in Statistics, Fall 2022

Lecture: Tuesdays and Thursdays, 11:00am-12:30pm, 310 Soda
Instructor: Prasad Raghavendra
Office hours: Tuesday 1:30-2:30pm

Course Description

In this course, we will explore the tractability of computational problems arising in high-dimensional statistics. Specifically, we will study

A tentative list of topics include the following:


Algorithmic Tools:

Evidence of intractability

Ideas from statistical physics:


Scribe notes: (link)(last update Sept 14)

Mean Estimation

Sum-of-Squares SDPs

Low-rank Data


Lower bounds

Project presentations


The class is aimed at graduate students specializing in theoretical computer science,statistics or related areas. A solid background in probability and linear algebra is an absolute must.



If you are interested in taking the class, please drop me an email with the subject line 'CS294 Enrollment’ along with details of what graduate program and research group you belong to, and relevant course/research experience if any.

Course Project:

Working in groups of two (or less), you are expected to find a potential direction for future research or an open problem, and write a short note (4-6 pages) on it. At the end of the semester, you will be giving a 15 minute whiteboard presentation of your question, to the rest of the class. Please sign up for your presentation time at the following spreadsheet:

We hope this gives an opportunity for you to explore a sub-area, assimilate the broad contours of existing literature, and most importantly exercise one of the most important skills as a researcher, that of asking questions. There are so many ways in which you can land on a question:

There are no wrong questions. Your questions don't need to be new either. But we hope that you are able to make a case to your peers that the question is interesting. So explore broadly and exercise your taste, to find a question that you think is interesting.

Here are some topics that can serve as starting points for you:

(The links are meant to be starting points for your research, and may not be exhaustive or latest