- Jan 31: First, organizational meeting
- Feb 7: Presentation of
Probabilistic Proof Systems (A Survey)

Part I: introduction to interactive proofs - Feb 14: Presentation of
Probabilistic Proof Systems (A Survey)

Part II: zero knowledge proofs - Feb 21: Presentation of
Probabilistic Proof Systems (A Survey)

Part III: probabilistically checkable proofs - Feb 28: Presentation of IP = PSPACE, part I
- Mar 7: IP = PSPACE, part II
- Mar 14: IP = PSPACE, part III
- Mar 21: Spring Vacation
- Mar 28: Presentation of Private coins versus public coins in interactive proof systems.
- Further presentations will be announced...

Some introductory text to interactive proofs:

- S. Arora. Around the PCP Theorem. Lecture notes.
- O. Goldreich. Introduction to Complexity Theory. Lecture notes.
- O. Goldreich. Foundations of Cryptography (fragments of a book).
- O. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
- O. Goldreich. Probabilistic Proof Systems (A Survey).
- O. Goldreich. 3 texts on Probabilistic Proof Systems.
- C. H. Papadimitriou Computational Complexity. Addison-Wesley, 1994.

The two papers that introduced interactive proofs:

- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In STOC 85, 291-304, 1985. (See also SIAM Journal on Computing 18:186-208, 1989.)
- L. Babai. Trading group theory for randomness. In STOC 85, 421-429, 1985. (See also L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences 36:254-276, 1988.)

Interactive proofs and complexity:

- S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In STOC 86, 59-68, 1986.
- L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive proofs. In Computational Complexity 1(1):3-40, 1991.
- U. Feige and L. Lovasz. Two-prover one-round proof systems: their power and their problems. In STOC 92, 733-744, 1992.
- A. Shamir. IP = PSPACE. Journal of the ACM 39(4):869-877, 1992.
- A. Shen. IP = PSPACE: simplified proof. Journal of the ACM 39(4):878-880, 1992.
- A. Condon and R. Ladner. Interactive proof systems with polynomially bounded strategies. Journal of Computer and System Sciences 50:506-518, 1995.

Interactive proofs and hardness of approximation:

- C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences 43:425-440, 1991.
- L. Babai. Interactive proofs and approximation. In ISTCS 93, 266-274, 1993.
- C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM 41(5):960-981, 1994. (reserved)
- M. Bellare and M. Sudan. Improved non-approximability results. In STOC 94, 184-193, 1994.
- U. Feige and J. Kilian. Two prover protocols - low error at affordable rates. In STOC 94, 172-183, 1994.
- U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43(2):268-292, 1996.
- S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM 45(3):501-555, 1998.
- M. Bellare, O. Goldreich and M. Sudan. Free bits, PCPs, and nonapproximability - towards tight results. SIAM Journal on Computing 27(3):804-915, 1998.

Interactive proofs and cryptography:

- M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: how to remove intractability assumptions. In STOC 88, 113-131, 1988.
- O. Goldreich and E. Kushilevitz. A perfect zero-knowledge proof for a problem equivalent to discrete logarithm. In Crypto 88, 1988.
- O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM 38(1): 691-729, 1991.
- M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, J. Kilian, S. Micali and P. Rogaway. Everything provable is provable in zero-knowledge. In Crypto 88, 1988.
- D. Lapidot and A. Shamir. A one-round, two-prover, zero-knowledge protocol for NP. In Crypto 91, 1991.
- C. Dwork, U. Feige, J. Kilian, M. Naor, and S. Safra. Low Communication, 2-prover zero-knowledge proofs for NP. In Crypto 92, 217-229, 1992.
- U. Feige and J. Kilian. Two prover protocols - low error at affordable rates. In STOC 94, 172-183, 1994.
- R. Canetti, O. Goldreich, S. Goldwasser and S. Micali. Resettable zero-knowledge. In STOC 00, 235-244, 2000.