### 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.

(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