CS 860, Fall 2016: Syllabus

To be updated as we go.

Sept. 9

Review/orientation: Turing machines, circuits, alternation, etc.

Reading: A. Chandra, D. Kozen, L. Stockmeyer, "Alternation", J. Assoc. Comput. Mach. 28 (114–133) 1981.

Sept. 14, 16

Reading (updated reference):
R. Karp, R. Lipton, "Turing machines that take advice," L'Enseignement Mathématique 28:2 (1982) 191–209.

Presenter: Jan Gorzny.

Sept. 21, 23

S. Goldwasser, M. Sipser, "Private Coins versus Public Coins in Interactive Proof Systems," in J. Hartmanis, 18th Annual ACM Symposium on Theory of Computing (STOC), 1986, pp. 59–68;

and

C. Lund, L. Fortnow, H.J. Karloff, N. Nisam, "Algebraic Methods for Interactive Proof Systems," J. Assoc. Comput. Mach. 39 (1992) 859–868.

Sept. 28, 30

A. Shamir, "IP=PSPACE", J. Assoc. Comput. Mach. 39 (1992) 869–877; and A. Shen, "IP=PSPACE: Simplified Proof, J. Assoc. Comput. Mach. 39 (1992) 878–880.