Selected Topics in Computational Complexity
This course deals with the problem of studying the algorithmic complexity of finding a near-optimal solution to optimization problems.
To illustrate, say we are given an instance of a 3CNF formula.
It is NP-hard to decide whether the formula is satisfied or not.
But how about deciding whether there exists an assignment that satisfies 99% of the constraints? Is it plausible?
In this course we will (hopefully) prove the PCP theorem, asserting that the above task is NP-hard.
Throughout the course we will encounter some basic objects in the study in theoretical computer science including: expanders graphs, Fourier transform and error correcting codes.
Time: Convention by e-mail during the week of October 20th, the first lecture will take place in the week of Novmber 3rd.
Location: Malá Strana.