Schedule for Spring 2001



Topic: Interactive Proofs

For those that did not attend my presentation of this subject in the fall term: Interactive proofs have to do with the problem of "How to convince?". The assumption is to have an omniscient prover that can help one to find answers to otherwise intractable problems, but the demand is to be at least CONVINCED by the prover that his answer is correct. It turns out that this can be a difficult task...

Meetings:

The meetings will take place every Wednesday at 4 p.m. in NEB 325.

Papers revolving around interactive proofs:

If you find an interesting paper you would like to read (as a single or a group) and present (as a whole or in part) in a meeting, let me know and I reserve it for you. You can get credit for your work if you want to by registering for the Seminar in Theory (number 600.771, see also the spring 01 course offerings of the CS department).

Some introductory text to interactive proofs:
The two papers that introduced interactive proofs:
Interactive proofs and complexity:
Interactive proofs and hardness of approximation:
Interactive proofs and cryptography: