The theory of Probabilistically Checkable Proofs; Non-approximability results for NP optimization problems (a survey)

admit a quick (logarithmic time) randomized checking both of the code
and a statement about its content.
A surprising consequence of the existence of such codes is
that finding approximate solution to certain optimization problems is
as hard as solving them exactly. (During the reduction from the
exact problem to the approximate one the instance size may
polynomially blow up.)
Since the first results of this type many approximation
problems have been shown to be hard using this framework.
This talk reviews old and new results coming from the PCP theory
and gives a glimpse into its methods.