6.S896 Algorithmic Statistics

Introduction to algorithms and computational complexity for high-dimensional statistical inference problems, with focus on provable polynomial-time guarantees. Covers modern algorithm design techniques via convex programming and Sum of Squares method, graphical models as a language to describe complex but tractable high-dimensional learning problems and associated learning algorithms, and basics of complexity for statistical problems, including statistical query and low-degree lower bounds and reductions.