Computer Science
|
Computational Complexity Theory0368.4105.01 |
Fall 2010 |
Lectures
|
Monday 13:00-16:00, Melamed 006 |
||||||||||||||
Instructor |
Muli Safra | Schreiber 319 | 6405371 | ||||||||||||||
T.A |
Jenny Falkovich Aviad Rubinstein |
||||||||||||||
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 |
||||||||||||||
Textbooks |
Main
references:
|
||||||||||||||
Requirements |
Attendance, homework assignments | ||||||||||||||
Prerequisites |
Computational models, Algorithms | ||||||||||||||
Previous Exams |
Last year quiz Last year moad a More previous exams in our course |
||||||||||||||
Other links |
A compendium
of NP-complete
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" Bonus: "Subset-Sum" Presentation from Aviad's tutorial on 25/11: Gap Problems 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 |