Hardness of Approximation

Hardness of Approximation is one of the most active subfields of complexity theory and has been making steady progress in establishing which problems admit polynomial time approximation algorithms (up to reasonable hardness assumptions). For many problems, matching lower and upper bounds on their polynomial-time approximability have been shown, proving that often very simple algorithms -such as the algorithm of Goemans-Williamson or random sampling of a solution- achieve best-possible approximation ratios. This course will focus on giving a working understanding of the current state of the field, focusing on some standout results that represent well the standard techniques, as well as some applications of these foundational theorems.

Concretely the goal is to work on the following tentative list of topics:

• Irit Dinur's proof of the PCP-theorem
• Håstad's tight inapproximability theorems for some MaxCSPs
• Fourier Analysis of Boolean Functions and Dictatorship Testing
• Tight inapproximability of Max-Cut up to the Goemans-Williamson threshold under the Unique Games Conjecture

The course will be given in English; lecture notes will be available. Sources for the course will include the following textbooks and articles:

• Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (2007)
• Johan Håstad. Some optimal inapproximability results. Journal of the ACM (2001)
• Subash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? Siam Journal on Computing (2007)
• Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press (2014); ArXiv 2021