Subhash Khot: Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games TheoremComputer 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.
Shayan Oveis Gharan: Polynomial Paradigm in Algorithm DesignIn 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.
Daily scheduleLectures 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, "group Africa/Asia/Australia/Europe": each day Tue-Sat, 8:00-9:30UTC
Exercise classes, "group Americas": each day Mon-Fri, 20:30-22:00UTC
(We may have additional groups 6:30-8:00UTC and 22:00-23:30UTC if needed.) The lectures will be streamed, and posted on youtube (and another platform which is available also in countries where youtube is not) within 2 hours after the lecture. The lectures are public whereas the exercise classes are for registered participants only.