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 2: A strategy towards proving the PCP theorem, abstracting out the steps, testing zeroeness of a polynomial is enough, zero-on-variety test. This talk will be based on parts from https://eccc.weizmann.ac.il/report/2025/165/ and https://eccc.weizmann.ac.il/report/2026/134/. These are joint works with Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard.