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.
Some relevant primary literature is listed below.
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)
Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press (2014); ArXiv 2021