It is well-known, by now, that for several NP-complete problems, even computing approximate solutions remains a computationally infeasible problem. This phenomenon, known as "hardness of approximation" is closely tied to constructing proofs for NP-statements that can be checked very efficiently by a probabilistic verifier. In the last twenty-five years, there have been several influential results on this topic, with connections to many areas in computer science and mathematics.  The "Unique Games Conjecture" has been proposed towards making further progress, leading to some unexpected results and connections. The talk will give a high level survey of all these developments.