Research Experiences for Undergraduates (REU) Seminar

Topic: Testing and Checking
Speaker: Mario Szegedy, Associate Professor in Computer Science, Rutgers University
Date and time: Friday, June 25, 2001, 12:00 noon
Location: 12:00 noon, CoRE Building, Room 301 (CoRE A) Rutgers University

Lunch will be served.


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