**Lecture:** Tuesday 11:00am-12:30pm, 310 Soda

**Instructor:** Prasad Raghavendra

**Office hours:** Tuesday 2:30-3:30pm

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

General techniques for designing efficient (i.e., polynomial-time) algorithms for these problems.

Conjectured computational barriers that arise among these problems and broad approaches to provide evidence of computational intractability.

A tentative list of topics include the following:

Problems:

Robust and heavy-tailed statistics: mean estimation and linear regression.

Mixture models, learning mixtures of Gaussians.

Stochastic block models, community detection.

Sparse PCA.

Matrix and tensor completion.

Algorithmic Tools:

Spectral methods & filtering.

Sums-of-squares semi-definite programming

Belief propagation

Approximate message passing

Evidence of intractability

Computational-statistical gaps.

Low degree hardness

Overlap gap property

Statistical query lower bounds.

Ideas from statistical physics:

Cavity Method

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.

Scribing: one or two lectures 40%

Project: In groups of 2 or 3, write a survey on a topic of your choice : 40%

Class participation 20%

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.