Computer Science

Computational Complexity Theory0368.3168.01 
Winter 2011/12 
Lectures

Monday 13:0016:00, Melamed 006 

Instructor 
Muli Safra  Schreiber 319  6405371  
T.A 
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 Powerpoint presentatiosn for some of last year's tutorials 

Textbooks 
Main
references:


Requirements 
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.  
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. 
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 NLCompleteness 

Nov 28  Dec 1  C vs coC Space vs Time Approximations 

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 