CS 496: Topics in Algorithmic Statistics, Winter 2026
Basic info
Course description: This is a graduate topics course on algorithmic statistics, focusing in particular on techniques for proving computational hardness of high-dimensional statistical problems.
Many modern statistical tasks are high-dimensional, which makes it a challenge to develop algorithms for them that are both computationally and statistically efficient. Recent developments in algorithmic statistics have made significant advances in both the positive (developing such algorithms) and negative (providing evidence for impossibility) directions. In particular, several canonical problems exhibit so-called information-computation gaps: regimes where the problem is information-theoretically solvable, yet (conjecturally) there is no efficient algorithm to do so.
This course focuses on techniques for providing evidence for such computational hardness. Specifically, the course will dive into three such methods which have received significant attention lately: the low-degree polynomial framework, the overlap gap property, and average-case reductions.
Goals: The goals of the course are three-fold: (1) to give an overview of recent research progress in the area; (2) to highlight ideas and techniques that are broadly useful, enriching students' technical tool box; and (3) to highlight open problems and create excitement about future research in the area.
Prerequisites: General mathematical maturity. More specifically, familiarity with probability, linear algebra, statistics, and algorithms. Please contact the instructor with questions.
Instructor: Miklos Z. Racz
Lecture time and location: MW 2:00 pm - 3:20 pm, Tech M120
Office hours: time TBD, 2006 Sheridan Rd, Room 108
Schedule
Tentative schedule and outline of topics covered:
- Weeks 1 - 2: Introduction and overview: canonical problems (e.g., planted clique), fundamental statistical and computational limits, information-computation gaps.
- Weeks 3 - 4: The low-degree polynomial framework.
- Weeks 5 - 6: The overlap gap property and its algorithmic implications.
- Weeks 7 - 8: Average-case reductions.
- Weeks 9 - 10: Finale: student presentations.
Grading and course policies
Grading: The course grade will be based on the following breakdown:
- participation 20%
- HW 30%
- paper presentation 50%
Paper presentation: Every student will pick a recent research paper and prepare a 20 minute presentation on it. The last couple of weeks of the course will be devoted to student presentations. A large list of possible papers will be provided before the start of the course.
Resources
The course will combine material from a number of recent lecture notes and surveys, as well as recent research papers. These include (all freely available online):
- Alexander S. Wein, Computational Complexity of Statistics: New Insights from Low-Degree Polynomials, Survey, 2025. [ arxiv ]
- Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira, Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio, ISAAC Congress (International Society for Analysis, its Applications and Computation), 2019. [ arxiv ]
- David Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures, Proceedings of the National Academy of Sciences (PNAS), 118 (41) e2108492118, 2021. [ arxiv ] [ PNAS ]
- Ilias Diakonikolas, Daniel M. Kane, Algorithmic High-Dimensional Robust Statistics, Cambridge University Press, 2023. [ online ]
- Sebastien Roch, Modern Discrete Probability: An Essential Toolkit, Cambridge University Press, 2024. [ online ]
Back to Teaching Home