Computational Complexity Theory
|| Monday 13:00-16:00, Melamed 006
||Muli Safra | Schreiber 319 | 6405371|
|| Jenny Falkovich
|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
||Attendance, homework assignments|
||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.
Presentations from Aviad's tutorial on 4/11:
"Subgraph Isomorphism" and "Shortest Path with Forbidden Pairs"
Presentation from Aviad's tutorial on 25/11:
Presentation from Aviad's tutorial on 16/12:
Gap Preserving Reductions
Presentation from Aviad's tutorial on 30/12:
Probabilistic Time Classes
Presentation from Aviad's tutorial on 20/1:
Review before the exam
|Date||Class Topic||Date||Class Topic|
|Oct 18||Oct 21|
|Oct 25||Oct 28|
|Nov 1||Nov 4|
|Nov 8||Nov 11|
|Nov 15||Nov 18|
|Nov 22||Nov 25|
|Nov 29||Dec 2|
|Dec 6||Dec 9|
|Dec 13||Dec 16|
|Dec 20||Dec 23|
|Dec 27||Dec 30|
|Jan 3||Jan 6|
|Jan 10||Jan 13||RL-basics|
|Jan 17||Jan 20|