Probabilistically checkable proofs

Can a proof be checked without reading it? That certainly seems impossible, no matter how much reviewers of mathematical papers may wish for this. But theoretical computer science has shown that we can get very close to this objective! Namely random consistency checks could reveal errors in proofs, provided one is careful in choosing the format in which proofs should be written. In this article we explain this notion, constructions of such probabilistically checkable proofs, and why this is important to all of combinatorial optimization.National Science Foundation (Awards CCR-0726525 and CCR-0829672