Course Announcement: PCPs and Limits of approximation algorithms - Winter/Summer Semester (2022-23)

Time: Fri 9:30-13:00 (w/ a 30 min break 11:00-11:30)
Location: A201
Instructor:
Homepage: http://tifr.res.in/~prahladh/teaching/2022-23/pcps

CSS.330.1: PCPs and Limits of approximation algorithms

Course Outline

The theory of NP-completeness is one of the cornerstones of complexity theory in theoretical computer science. The celebrated PCP theorem established that several fundamental optimization problems are not only hard to solve exactly but also hard to approximate. From Khot's seminal work of 2003, the unique games conjecture (UGC) emerged as a powerful hypothesis that has served as the basis for a variety of optimal inapproximability results. More recently, we have seen that the study of geometry of certain high-dimensional structures (eg, Grassmanian, Johnson etc) have led to resolution of weaker forms of the UGC and construction of linear-sized locally testable codes.

Syllabus

In this course, we will see some of the recent developments in the area of probabilistically checkable proofs, unique games and high-dimensional expanders. In particular, Topics covered will include a mixture of earlier and very recent work, such as:

For a flavor of the topics that will be covered, see the previous avatar of this course at TIFR/IMSc (Limits of Approximation Algorithms (TIFR/IMSc course, 2010 Winter/Summer semester, PCPs and Limits of approximation algorithms (two module course) - Winter/Summer Semester (2014-15) and a workshop on the same topic organized at DIMACS (http://dimacs.rutgers.edu/Workshops/Limits/).

Grading

The grading will be based on problem sets (3-4 of them through the course), class participation and paper/project presentation. The split will be as follows: Problem Sets (60%) + Class Participation (20%) + Project Presentation (20%).

Prerequisites

A familiarity with the list of topics covered in the CSS.203.1 Computational Complexity Course.

Instructor:

Prahladh Harsha