Humans are pretty good at coming up with heuristics that solve hard problems almost optimally. In the 1980s and 1990s, researchers began asking whether it was possible to design efficient algorithms that approximately solve hard problems, such as NP-hard problems. For some problems, there was success, for others, not so much. This led to a fundamental question: Can we rule out the existence of good approximation algorithms?
There were some lower bounds, but a general methodology for proving such results was lacking. Then came the PCP theorem, which provided a powerful new way to prove hardness of approximation and has since become a go-to hammer for establishing limits on approximation algorithms.
In this mini course, we will start with the definition of a NP, see why it naturally leads to inapproximability results, and then prove the PCP theorem (or at least a weaker version of it). The course will consist of 2 talks, with the following rough outline.
Talk 1: Introduction to PCP, Gap Problems, Hardness of approximation for Gap problems, Intuition behind why even the PCP theorem is true. Finally, if time permits, then a strategy towards the proof of PCP theorem.