Computer Science
Tel-Aviv University

Computational Complexity Theory

0368.4105.01

Fall 2010


Announcements


Presentations


Homework assignments


Some Information

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:
[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
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

Schedule

Date Class Topic Date Class Topic
Oct 18
  • Introduction
  • Turing Machines
  • Oct 21
  • Complexity Functions
  • Turing Machines
  • Oct 25
  • Turing Machines
  • Reduction
  • Oct 28
  • P, NP and coNP - basics
  • Nov 1
  • Cook-Levin Theorem (3SAT is NPC)
  • Nov 4
  • Examples of NPC problems
  • Nov 8
  • Space Complexity
  • Nov 11
  • Two definitions of NL
  • Nov 15
  • Savitch's Theorem
  • Immerman's Theorem
  • Nov 18
  • Padding Argument
  • Immerman's Theorem (proof)
  • Nov 22
  • Approximations
  • Gap Problems
  • Nov 25
  • Gap Problems
  • Nov 29
  • Approximations
  • Gap Problems
  • Dec 2
  • Savitch's Theorem
  • Immerman's Theorem
  • Dec 6
  • Quiz
  • 2SAT
  • Concentration of Measure
  • Dec 9
  • Greedy Algorithm for Derandomailzation
  • Diagonalization Method
  • Dec 13
  • PCP
  • Dec 16
  • Gap Preservering Reductions
  • Dec 20
  • Space Complexity
  • Concentration of Measure
  • Dec 23
  • Examples of CSG
  • IS is NP-hard for any factor
  • Dec 27
  • PH & BPP
  • Zero Knowledge Proofs
  • Dec 30
  • BPP(p,q)
  • RP
  • Jan 3   Jan 6
  • Uniqueness in Triplets
  • UG
  • Jan 10   Jan 13 RL-basics
    Jan 17   Jan 20