Lunch will be served.
(PUBLIC INVITED)
Checking, testing and verifying are different sub-topics in the theory of computer science, but they are bound together by the same overall theme: a computationally limited user (also called verifier or checker) wants to get convinced that an object (for instance, a mathematical proof) has the desired features. While the verifier is too limited to produce the object by himself (or even to read its bits entirely), he can still check its properties with some, or complete certainty (depending on the model). Major breakthroughs of the theory of computer science are associated with this paradigm. Among them are: the theory of NP, Blum checking, Zero knowledge proofs, Probabilistically checkable proofs, Artur-Merlin games and Combinatorial property testing. We try to present as many of these notions as possible in a one hour talk in an easy, informal manner.
Return to June 2001 calendar