Computational Complexity Theory
|| Monday 13:00-16:00, Melamed 006
||Muli Safra | Schreiber 319 | 6405371|
|Lecture notes on the web||PowerPoint presentations
used in Safra's lectures.
Previous courses in TAU:Spring 2007, Spring 2008, Fall 2008
Oded Goldreich from Weizmann
Powerpoint presentatiosn for some of last year's tutorials
||Attendance, homework assignments, midterm||Note: Students who do not submit at least 90% of homework assignments on time will not be allowed to take the exam.|
||Computational models, Algorithms|
||Last year quiz
Last year moad a
More previous exams in our course
problems and what's known about them.
A compendium of problems in higher levels of the hierarchy, part I and part II.
The zoo of all(?) known complexity classes.
|Date||Class Topic||Date||Class Topic|
|Oct 31||Nov 3||NP|
|Nov 7||Nov 10||L vs PSPACE|
|Nov 14||Nov 17|
|Nov 21||Nov 24||Padding
|Nov 28||Dec 1||C vs co-C
Space vs Time
|Dec 5||Dec 8||Gap Problems|
|Dec 12||Dec 15||Gap Preserving Reductions|
|Dec 19||Dec 22|
|Dec 26||Dec 29||Soundness Amplification|
|Jan 2||Jan 5||Probabilistic Time Classes|
|Jan 9||Jan 12|
|Jan 16||Jan 19||More Probabilistic Classes (BPL, RL, IP)|
|Jan 23||Error Correcting Codes||Jan 25||Error Correcting Codes
Notes on rates and distances
|Jan 30||Feb 2|