MIT Department of Electrical Engineering & Computer Science

EECS Fall 1997 Catalogue Supplement

6.968 Seminar in Complexity Theory (G)

T 4-6, NE43-318
Prof. Shafrira Goldwasser, NE43-332, x5914
2-0-7

This class covers recent (state of the art) results in the area of complexity theory and theory of cryptography. In particular, the three central topics for this seminar are:

1. Computational difficulty of integer lattice problems and how they can be applied to cryptography.

2. Computational complexity aspects of Statistical and Perfect Zero Knowledge.

3. Upper bounds for approximation problems using semi-definite-programming.