Research Experience for Undergraduates (REU) Seminar

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

Lunch will be served.


Checking, testing and verifying are diffent 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 assiciated 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 REU home page