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.

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.

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. |