Computer Science
Tel-Aviv University

Computational Complexity Theory


Winter 2011/12



Homework assignments

Some Information


Monday 13:00-16:00, Melamed 006

Muli Safra | Schreiber 319 | 6405371

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

Main references:
[AB] Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak
[S] Introduction to the Theory of Computation, by Michael Sipser (1st or 2nd edition only)
[P] Computational Complexity, by Christos H. Papadimitriou
Other textbooks:
[MOV] Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone.
[MR] Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan
[V] Approximation Algorithms, by Vijay V. Vazirani
[CLR] Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
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
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.


Date Class Topic Date Class Topic
Oct 31
  • Introduction
  • Turing Machines
  • Nov 3 NP
    Nov 7
  • Basic Complexity Classes
  • Poly-time reductions
  • Cook's Theorem
  • Nov 10 L vs PSPACE
    Nov 14
  • NP Completeness
  • Space Complexity
  • Nov 17
  • More NPC problems
  • Yet another NPC problem (if time permits)
  • Nov 21
  • Savitch
  • Immerman
  • Padding
  • Nov 24 Padding
    Nov 28
  • Immerman (Cont.)
  • Approximations
  • Dec 1 C vs co-C
    Space vs Time
    Dec 5
  • Gap Problems
  • The PCP Theorem
  • Dec 8 Gap Problems
    Dec 12
  • Gap Preserving Reductions
  • Constraint Satisfaction Graphs
  • Dec 15 Gap Preserving Reductions
    Dec 19
  • 2SAT
  • Gap Amplification
  • Dec 22
    Dec 26
  • Gap Amplification (Cont.)
  • Concentration of Measure
  • Dec 29 Soundness Amplification
    Jan 2
  • TQBF is PSPACE Complete
  • PH
  • BPP
  • Jan 5 Probabilistic Time Classes
    Jan 9
  • BPP in \Sigma_2
  • RL
  • Jan 12
  • Derandomization
  • 2SAT is NL-Complete
  • Jan 16
  • Hardness of approximation for coloring
  • UG
  • 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
  • Random Walks (Cont.)
  • SDP
  • Feb 2
  • Error Correcting Codes (Cont.)
  • Questions from a previous exam