Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2009


Announcements


Homework assignments

Instructions and exercises

Out Due Questions
3/3/2009 17/3/2009 Homework 1
17/3/2009 24/3/2009 Homework 2
24/3/2009 31/3/2009 Homework 3
31/3/2009 21/4/2009 Homework 4
05/5/2009 19/5/2009 Homework 5
19/5/2009 02/6/2009 Homework 6
31/5/2009 14/6/2009 Homework 7
14/6/2009 03/7/2009 Homework 8


  • Homework Submission



  • Lecture notes

  • Time complexity

  • Some Information

    Lectures Group 1: Tuesday 10:00-13:00, Schreiber 006
    Group 2: Monday 10:00-13:00, Shenkar 222
    Recitations: Tuesday 15:00-16:00 Kaplun 118,
    16:00-17:00, 18:00-19:00 Schreiber 008.
    Instructors

    Oded Regev | Schreiber 103 | 6407996 | Office hour: Monday 13:00
    Muli Safra | Schreiber 319| 6405371
    T.A
    Ido Ben-Eliezer | Schreiber Open Space | 6405398
    Ishay Haviv
    Lecture notes PowerPoint presentations used in Safra's lectures.
    Previous courses in TAU:Spring 2007, Spring 2008, Fall 2008
    Oded Goldreich from Weizmann (see also here)
    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
    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.
    Previous exams in our course

    Schedule

    Week Date Class Topics
    1 Mar 2, Mar 3
  • Administration
  • Historical remarks
  • Computability[AB1, S part II]: languages, the model of computation and its robustness, the universal turing machine, uncomputable functions
  • Time complexity [AB2,S7]: the classes P and NP
  • Mar 3 P, NP and coNP are closed under the Kleene star.
    Mar 9 Bonus Class: Error-Correcting-codes, in particular the Reed-Solomon code and the Hadamard code.
    2 Mar 16, Mar 17
  • The class NP
  • problems in NP
  • alternative definitions of NP
  • reductions and NP-completeness
  • Mar 17 Karp reductions versus Cook reductions.
    3 Mar 23, Mar 24
  • TMSAT is NP-complete [AB2]
  • The Cook-Levin theorem [S7.4]
  • How to deal with NP-complete problems; Decision vs. Search [AB2.5]
  • what if P=NP?
  • More complexity classes: coNP [AB2.6]
  • EXP, NEXP
  • Mar 24
  • Decision vs. Search of 3-Colorability
  • If there exists a unary NP-complete language then P=NP [P 14.2]
  • 4 Mar 30, Mar 31
  • IIf EXP!=NEXP then P!=NP
  • Σ2P, Π2P [AB5.1]
  • If P=NP then P=Σ2P
  • The time hierarchy theorem [AB3.1]
  • Oracle machines and the limits of diagonalization (oracle A such that PA = NPA and oracle A such that PA ≠ NPA) [AB3.5]
  • Mar 31
  • PP is equal to P, but EXPEXP is not equal to EXP
  • An example for a language in Pi2P
  • 5 Apr 20, Apr 21
  • Definitions L, NL, PSPACE
  • CONN is NL-complete, Savich's Theorem
  • Apr 21
  • L and NL, 2SAT is coNL-complete [AB]
  • Apr 27 Bonus Class: Communication Complexity
    6 May 4, May 5
  • Nondeterministic-to-Deterministic Sisyphean simulation
  • The reduction from 3SAT to CLIQUE
  • May 5
  • Space Complexity
  • L vs NL
  • NP vs PSPACE
  • May 8 Mid Term Exam
    7 May 11, May 12
  • TQBF is PSPACE-complete [AB4.3](more PSPACE-complete problems here)
  • Optimization problems, approximation algorithms, 2-approximation for Vertex Cover (VC) via maximal matching [P13.1].
  • Linear programming, Integer programming, VC ≤p IP. LP is in P and IP is NP-hard.
  • Relaxations. Rounding. A 2-approximation for VC via LP relaxation.
  • May 12
  • Approximation of TSP with triangle inequality
  • 8 May 18, May 19
  • Approximation algorithms
  • Set-Cover
  • Gap-problems and the PCP theorem
  • May 19
  • gap problems, and hardness of Max-2SAT
  • 9 May 25, May 26
  • gap problems
  • gap-preserving reductions
  • Constraint-Satisfaction-Graphs
  • amplification and hardness of approximating Independent-set to within any constant
  • May 26
  • VC vs IS
  • An example of the probabilistic method
  • CSG
  • 10 June 1, June 2
  • Hardness of approximation for Independent-set
  • CLIQUE and Chromatic-Number of a graph
  • June 2
  • CSG and hardness of approximating IS and the chromatic number
  • 11 June 8, June 9 Random Computations:
  • BPP in Sigma2
  • Random walks, undirected-connectivity in Random LOGSPACE
  • June 9
  • hardness of approximation of the chromatic number
  • 12 June 15, June 16
  • The Chernoff bound
  • LP for Set Cover and randomized rounding
  • Goemans-Williamson SDP for Max Cut and randomized rounding
  • June 16
  • the conditional expectation method
  • Karger's mincut algorithm