The Tale
Of the PCP
Theorem
In the 1970s, the landscape of algorithms research changed ramatically. It was discovered that an efficient algorithm for any one of the numerous innocent-looking algorithmic problems would imply something that sounds too fantastic
to be true. An algorithm given a provable mathematical
statement, efficiently finds the shortest proof for the statement.

connect nodes belonging to different parts. As it turns out, there is a better algorithm for Max-Cut, one that finds a partition in which the fraction of links between different parts is about 0.878 times the optimum (i.e., a ~0.878 approximation). This algorithm was discovered by Michel Goemans and David Williamson in the 1990s and it has not been improved upon for the last two decades.

While Max-Cut has an approximation to within a constant factor, for other problems such approximations were not found. Sometimes the best approximation depended on the size of the input, so as the input size grew bigger, the approximation worsened. In sharp contrast, some problems could be approximated arbitrarily well (to within 0.9999… 9 for any number of 9s). This left researchers wondering whether they were way off with the other problems. Could there exist better approximation algorithms that had not been discovered? The salvation came from an unexpected source.

 

parts is at least half of the maximum (in technical terms this is a “½-approxi- mation”): Pick the partition at random. That is, for each node flip a coin. If the coin shows “heads,” put the node in the first part, and if coin shows “tails,” put the node in the second part. The probability that the two endpoints of a link belong to different parts is exactly half. Hence, on average, half of all links will

HARDNESS OF APPROXIMATION

By the early 1990s researchers realized how to show NP-hardness of approximation problems. This explained the little success algorithmists had with improving their approximations for some problems.

The conceptual path that led to this breakthrough was long and intertwined. It started a decade earlier with the works of Goldwasser, Micali, and Rackoff on zero-knowledge proofs, and Babai’s work on interactive proofs. Back then, no one foresaw these could have any implications to approximation algorithms, but this is what ended up happening.

Both works suggested models for proving and checking proofs that were different from the standard model of writing down a proof, and checking it step by step. The new models viewed theorem proving as a discussion between a prover and a verifier. The verifier may ask the prover questions, and the questions may be randomized. If the verifier’s impression of the validity of the proof is correct with probability, say, 0.99, they said, this is good enough.

Those models and related models then became the subject of study and