Background The NPcompleteness of important optimization problems focused research effort on the design of approximation algorithms. Some problems succumbed to approximation. Others, however defied all efforts to either find good approximation algorithms or to show such algorithms dont exist. A breakthrough came in a 1991 paper by Feige, Goldwasser, Lovasz, Safra, and Szegedy. They used results on probabilistically checkable proofs PCPs to show that Max Clique is hard to approximate. Research has since then expanded to apply their approach to other problems, and to improve the results. Today, the known results are quite amazingly broad and strong, and research is still advancing rapidly.

Website: http://www-cse.ucsd.edu/users/mihir/pcp.html