CS G399: Gems of Theoretical Computer Science; Spring 2009

Instructor:  Emanuele Viola

Meetings: Tuesday 10:30 - 12:10 in Room 166 WVH map and Friday 1:35 PM - 3:15 PM Room 429 Ryder Hall (RY), 11 Leon St., campus map, map.

Office Hours: by appointment.

Course Description

This course covers some of the most exciting and recent progress in theoretical computer science. It presents state-of-the-art results on active research areas, and teaches related proof techniques. A tentative list of topics includes: Lower bounds for constant-depth circuits.
The Nisan-Wigderson pseudorandom generator.
Cryptography in constant parallel time.
The complexity of Nash equilibria.
Undirected connectivity in logarithmic space (SL = L).
Communication complexity.
Primes is in P.
Fast matrix multiplication.


No background is required for this class. However, this is a theoretical course with emphasis on theorems and proofs, so ``mathematical maturity'' is expected.

Each student is required to scribe (#lectures/#students) lectures.

Class schedule

Content of future lectures is tentative.
 Lecture  Content Lecture notes
Extra
Jan 6 Overview of the course. Template for scribes. Sanjeev Arora and Boaz Barak's book on complexity.
Oded Goldreich's material on complexity, including his book.
Jan 9 Preliminaries: Probability, correlation, circuits, and pseudorandom generators. Lecture 1. Problem 1. (*)
Jan 13 The Nisan-Wigderson pseudorandom generator: I
Yao's next-bit predictor.
Lecture 2.  
Jan 16 The Nisan-Wigderson pseudorandom generator: II
Lecture 3. Problems 2,3. (*)
Jan 20 Parity requires large constant-depth circuits: Aspnes, Beigel, Furst, and Rudich's proof. I
 
Jan 23 Parity requires large constant-depth circuits: Aspnes, Beigel, Furst, and Rudich's proof. II
Lectures 4 and 5.  
Jan 27 Parity requires large constant-depth circuits: Aspnes, Beigel, Furst, and Rudich's proof. III
   
Jan 30 Parity has exponentially small correlation with small constant-depth circuits: Klivans and Vadhan's proof.
Lectures 6 and 7. Problem 4. (*)
Feb 3 Arithmetic in log-depth circuits: addition, iterated addition, multiplication.
Beame, Cook, and Hoover's log-depth circuits for division. I
Lecture 8.  
Feb 6 Beame, Cook, and Hoover's log-depth circuits for division. II
Proof of the weak prime number theorem.
Lecture 9.  
Feb 10 Valiant's result that log-depth linear-size is in depth-3 subexponential-size.
Lecture 10.  
Feb 13 Barrington's theorem.
Lecture 11.  
Feb 17 Applebaum, Ishai, and Kushilevitz's cryptograhy in constant depth: I
Lecture 12.  
Feb 20 Applebaum, Ishai, and Kushilevitz's cryptograhy in constant depth: II    
Feb 24 Applebaum, Ishai, and Kushilevitz's cryptograhy in constant depth: III
Lectures 13 and 14.  
Feb 27 Spectral graph theory.
Undirected reachability in randomized log space.
   
Spring break.   Problems 5,6. (*)
Mar 10 Undirected reachability in log space, Rozenman and Vadhan's proof: I
  Course on expanders by Linial and Wigderson.
Mar 13 Undirected reachability in log space, Rozenman and Vadhan's proof: II
   
Mar 17 Undirected reachability in log space, Rozenman and Vadhan's proof: III
Primes in P: I
Lectures 15-18 on undirected reachability in log space.  
Mar 20 Primes in P: II
  Andrew Granville's survey, Victor Shoup's book .
Mar 24 Primes in P: III Lectures 18-20 on Primes in P.  
Mar 27 Group-theoretic algorithms for fast matrix multiplication: I    
Mar 31 Group-theoretic algorithms for fast matrix multiplication: II    
Apr 3 Group-theoretic algorithms for fast matrix multiplication: III
Succinct data structures: I
Lectures 21-23 on matrix multiplication.  
Apr 7 Succinct data structures: II Lectures 23-24 on succinct data structures.  
Apr 10 Communication complexity    
Apr 14 Multiparty communication complexity: I    
Apr 17 Multiparty communication complexity: II Lectures 25-27 on communication complexity.  
Apr 21 Natural Proofs Lecture 28 on natural proofs.  

Problems (*)

Problems are optional and stated in the following continuously updated file: Problems. The above class schedule signals when a new problem is inserted in the file.