Computer Science

Computational Complexity Theory0368.4105.01 
Fall 2010 
Lectures

Monday 13:0016: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 NPcomplete
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: "SubsetSum" 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  RLbasics  
Jan 17  Jan 20 