Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 496: Topics in Algorithmic Statistics


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

Permission of Instructor

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.

  • This course fulfills the Technical Elective area.

REFERENCE TEXTBOOKS: N/A
REQUIRED TEXTBOOK: N/A
COURSE COORDINATORS: Prof. Miklos Racz
COURSE INSTRUCTOR: Prof. Miklos Racz Office hours: time TBD, 2006 Sheridan Rd, Room 108.