67802 - Computational Complexity (Spring 2006)
Teacher: Irit Dinur
Location: Sprinzak 216
Time: Wed 3-6
The course will cover topics in computational complexity.
Grade will be given based on a final project, due: 17-July-2006.
Some Online References
- Oded Goldreich's new book (draft).
- Sanjeev Arora and Boaz Barak's new book (draft).
- Luca Trevisan's notes from a course at Berkeley.
- Madhu Sudan's course at MIT.
Final Projects
Grades in the class will be based on a final project. Each student is expected to read paper/s related to a topic
of their choice (partial list below), and give an oral presentation accompanied by a written summary of 4-5 pages of the material.
The presentations will take place on one of two dates: 25/7/06 or 8/8/06, starting at 10:30am. Each presentation will be 30-40 minutes.
- (Yael?) Diagonalization: Time and Space and Nondeterministic Time Hierarchy Theorems
- (Mor, Yonatan) Diagonalization and its limitations: Oracles relative to which P=NP and P \neq NP
- (Or Sattath, Benny) Counting Problems: the permanent on 0-1 matrices is #P complete (Valiant's Theorem)
- (Elazar, Ayelet) Amplification of Hardness: XOR Lemmas
- (Ram Boukobza) Average Case Hardness of NP
- (Yura) Interactive Proofs: equivalence of private-coin and public coins in constant-round interactions
- (Elad) Statistical zero knowledge
- (Eliyahu, Matias) Concrete Computational Models: communication complexity