GISP 

Advanced Topics in The Theory of Computation

 

Semester II, 2000-2001

 

Syllabus

 

  1. Week 1 (Jan 24^th-26^th).  How can you represent a computer mathematically?  

     Turing Machines are presented as our standard model of computation. Various other models are shown to be equivalent to the Turing Machine (Sipser, chapter 3).

      Kevin Matulef presents...

 

2.   Week 2 (Jan 29^th-Feb 2^nd).   A powerful technique for proving the limits of computing.

      The “halting” problem, a famous problem that is “too hard” for any computer, is presented.  Particular emphasis is paid to the method of proof, “diagonalization.”  Later this method will be shown insufficient for proving an open problem in the field (Sipser, chapters 4 and 5)  The Post Correspondence Problem is shown to be undecidable.

        Darius Pierce and Stephen Canon present...

 

3.   Week 3 (Feb 5th-Feb 9^th).   

     The Recursion theorem.  Undecidability of Logical Theories (Sipser, Chapter 6).

 

4.   Week 4 (Feb 12^th-Feb 16^th).  Review of Computational Complexity.

     The time complexity classes P and NP, and the space complexity classes PSPACE, L, and NL are reviewed.  Examples are given of problems in each class. The notion of “complete” problems for NP, PSPACE, and NL is presented.  The notion of a reduction is also presented  (Sipser Ch 7 & 8).

 

5.   Week 5 (Feb 19^th-Feb 23^rd).  Further Results in Time and Space Complexity. 

The proof of an NP complete problem. Proof that CoNL = NL (Sipser Ch 7 & 8).

 

6.   Week 6 (Feb 26^th-Mar 2^nd).  Proving Problems to be Intractable.

     The hierarchy theorems are presented.  The notions of oracles and relativization are introduced.  Proof is given to show that diagonalization is not enough to prove P different than NP (Sipser, 9.1-2).

 

7.   Week 7 (Mar 5^th-Mar 9^th).  Alternation.

     Alternating Turing machines and the polynomial hierarchy are introduced, and elementary results are given (Sipser 10.3)

 

8.   Week 8 (Mar 12^th-Mar 16^th).  Randomness complicates the world of Complexity.

     Randomized complexity classes.  The class BPP is introduced (Sipser 10.2).

 

9.   Week 9 (Mar 19^th-Mar 23^rd).  Introduction to Cryptography.

     Mathematical Foundations of Cryptography (Goldreich, Chapter 1).

 

Spring Recess (Mar 24^th-Apr 1^st)

 

10.  Week 10 (Apr 2^nd-Apr 6^th).  Games of verifying information:  Introduction to Probabilistic proofs.

     Definitions and examples of Interactive and Zero-Knowledge proofs are given (Goldreich, Chapter 2.1, 3.1).

 

11.  Week 11 (Apr 9^th-Apr 13^th).  More on the power of Interactive Proofs.

     IP=PSPACE (Goldreich, Chapter 2.2).

 

12.  Week 12 (Apr 16^th-Apr 20^th).  Probabilistically Checkable Proofs.  

     Definition of probabilistically checkable proofs, and relation to approximation algorithms (Goldreich, Chapter 2.4).

 

13.  Week 13 (Apr 23^rd-Apr 26^th).  Pseudorandomness.

     Definitions of randomness.  The complexity theorists approach to defining randomness.  Examples and open problems (Goldreich, Chapter 3.1-3.4, 3.7).

 

Reading Period (Apr 27^th-May 8^th)

Final Paper Due, accompanied by short presentation.

 

Books

Sipser, Michael. Introduction to the Theory of Computation.  Boston: PWS Publishing Company, 1997.

Goldreich, Oded. Modern Cryptography, Probabilistic Proofs, and Pseudorandomness (Algorithms and Combinatorics, Vol 17).  Springer Verlag, 1997.

 

Note:  We also have for our reference an author’s copy of the soon to be published second edition of Oded Goldreich’s book.