PRAGUE SUMMER SCHOOL ON DISCRETE MATHEMATICS 2020

Subhash Khot: Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem

Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.

The course will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.

Study material

The overall summary of the course can be found in this video. An expository article about the 2-to-2 Games Theorem can be found here.

General preliminaries

Familiarity with the following concepts is necesary: (Pointers such as "L-5" refer to "Lecture notes" below) Lecture notes (you do not need to study these prior to the course, other than parts referred to above): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.

Preparations for lectures 4 and 5

Please watch the following youtube video.

Homework exercises

Shayan Oveis Gharan: Polynomial Paradigm in Algorithm Design

In this course we discuss the fruitful paradigm of encoding discrete phenomena in complex multivariate polynomials, and understanding them via the interplay of the coefficients, zeros, and function values of these polynomials. Over the last fifteen years, this perspective has led to several breakthroughs in computer science, and an unexpected bridge between seemingly distant scientific areas including combinatorics, probability, statistical physics, convex and algebraic geometry, and computer science has been built. In this course I plan to cover part of these developments with an emphasis on more recent developments specially connections to traveling salesman problem, matroids, high dimensional expanders and mixing time of random walks.

Study material

The overall summary of the course can be found in this video.

Preparatory material concerning polynomials, random spanning trees, random walks, and matroids.

Material for the School

Lecture notes: Day 1, Day 2, Day 3, Day 4, Day 5.

Homework assignments: Day 1, Day 2, Day 3, Day 4, Day 5.

[Link] to all hand-written notes created during the lectures.

Daily schedule

Lectures of Subhash Khot: each day Mon-Fri, 14:00-15:00UTC (7:00-8:00PDT/Vancouver, 8:00-9:00MDT/Denver, 9:00-10:00CDT/Minneapolis, 10:00-11:00EDT/New York, 15:00-16:00BST/London, 16:00-17:00CEST/Paris, 17:00-18:00MSK/Moscow)

Lectures of Shayan Oveis Gharan: each day Mon-Fri, 15:30-16:30UTC (8:30-9:30PDT/Vancouver, 9:30-10:30MDT/Denver, 10:30-11:30CDT/Minneapolis, 11:30-12:30EDT/New York, 16:30-17:30BST/London, 17:30-18:30CEST/Paris, 18:30-19:30MSK/Moscow)

Exercise classes, "Africa/Asia/Australia/Europe": each day Tue-Sat (!!!), 8:00-9:30UTC, split into two groups, "AAAEg1" and "AAAEg2"

Exercise classes, "Americas": each day Mon-Fri, 20:30-22:00UTC.

Zoom links (lectures)

Registered participants can join the lectures using Zoom (see Zoom links below). Each Zoom session can be started by clicking on the link in the table. Note that you need the passcode to join the meeting. The passcode will be sent to all registered participants prior to the School.
Monday, August 24
13:40UTC-15:00UTCWelcome (20mins)+Subhash Khot (Lecture 1)
15:30UTC-16:30UTCShayan Oveis Gharan (Lecture 1)
Tuesday, August 25
14:00UTC-15:00UTCSubhash Khot (Lecture 2)
15:30UTC-16:30UTCShayan Oveis Gharan (Lecture 2)
Wednesday, August 26
14:00UTC-15:00UTCSubhash Khot (Lecture 3)
15:30UTC-16:30UTCShayan Oveis Gharan (Lecture 3)
Thursday, August 27
14:00UTC-15:00UTCSubhash Khot (Lecture 4)
15:30UTC-16:30UTCShayan Oveis Gharan (Lecture 4)
Friday, August 28
14:00UTC-15:00UTCSubhash Khot (Lecture 5)
15:30UTC-16:30UTCShayan Oveis Gharan (Lecture 5)

Youtube channel

The lectures will be also streamed publicly live on Youtube channel PragueSummerSchool DiscreteMathematics where they will also be recorded. You can post live questions to the lecturers in the Youtube chat on that channel. However, note that there is an approximately 30 second delay in this "live" broadcast.

Zoom links (exercise classes)

Only for registered participants. Note that you need the passcode to join the meeting. The passcodes for each group are different and were sent to all participants assigned to their respective group prior on August 22 around 21:00UTC in an email with subject "Prague Summer School on Discrete Mathematics: Lectures and Exercise classes (group ...)". The exercise classes for both lectures are under the same link (the first ca 45 minutes of each session will be devoted to Subhash Khot's exercises, followed by 45 minutes devoted to Shayan Oveis Gharan's exercises).
Monday, August 24
20:30UTC-22:00UTC Americas 1
Tuesday, August 25
8:00UTC-9:30UTC AAAEg1 18:00UTC-9:30UTC AAAEg2 120:30UTC-22:00UTC Americas 2
Wednesday, August 26
8:00UTC-9:30UTC AAAEg1 28:00UTC-9:30UTC AAAEg2 220:30UTC-22:00UTC Americas 3
12:30UTC-13:30 A session on a solution of Exercise 1.5 of the Hardness of approximation course; no passcode required.
Thursday, August 27
8:00UTC-9:30UTC AAAEg1 38:00UTC-9:30UTC AAAEg2 320:30UTC-22:00UTC Americas 4
Friday, August 28
8:00UTC-9:30UTC AAAEg1 48:00UTC-9:30UTC AAAEg2 420:30UTC-22:00UTC Americas 5
Saturday, August 29
8:00UTC-9:30UTC AAAEg1 38:00UTC-9:30UTC AAAEg2 5