A survey on inapproximability

Not to infringe on the Complexity blog :), but I found this survey by Luca Trevisan at the ECCC to be a very well written birds-eye view of the developments in inapproximability from slightly before the main PCP results till now (in fact some of the results mentioned are to appear at FOCS 2004).

It covers the early attempts at showing approximability by gap-introducing reductions, spends a little time (although not a lot) on the growing body of work relating proof systems to inapproximability, and then spends a lot of time on developments post PCP.

What I like about it, as a non-expert in complexity, is that it explains some of the basic PCP-based methods for proving hardness very lucidly, using examples like clique and set cover. It also helps one understand the feverish developments in the field leading to the slew of optimal inapproximability results in the late 90s.

There has been a recent flurry of breakthrough complexity results, some of which are to appear at FOCS. The survey addresses some of these new results as well, and what they could imply for the knottier problems like vertex cover etc.

Probably one of the most interesting developments over the past few years is a set of hardness results that destroy the 5-class inapproximability hierarchy that people had thought to map out the space of approximations. New results showing tight log^* n hardness, log log n hardness, and even log² n hardness results indicate that approximation classes might be a lot finer than people had imagined.