Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Fall 2009


Announcements


Homework assignments

Instructions and exercises

Out

Due

Questions

23/10

9/11

Ex. 1

12/11 26/11

Ex. 2

19/11 3/12

Ex. 3

6/12 21/12

Ex. 4

21/12 4/1/2010 Ex. 5
6/1 21/1 Ex. 6
17/1 29/1 Ex. 7

 


Some Information

Lectures

Lectures: Monday 13:00-16:00 ,   Melamed 006 
Recitations: Thursday
13:00-14:00 Kaplun 118, 14:00-15:00 Orenstein 110

Instructors

Muli Safra| Schreiber 319 | 6405371 | Office hour: Monday 16:00-17:00
T.A.: Ido Ben-Eliezer | Schreiber Open Space ('Theory Room') | 6405398 | 

Grader: Tomer Levinboim

Lecture notes on the web

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:

[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

 


Old Presentations

1. Introduction

2. Preliminaries

3. Reductions

4. Cook Theorem

5. NP-complete Problems;

6. Paths

7. 2SAT

8. Space Complexity

9. Approximation Algorithms

10. TSP

11. Hardness of Approximation

12. Cryptography

13. The Polynomial-time Hierarchy and BPP

14. coNP and Primality

15. Random Walks

16. Zero Knowledge Proofs

 

 

Schedule

Week

Date

Class Topics

1

19/10/09

Complexity functions, definition and example of Turing Machine. (L)

1

22/10/09

The classes P,NP,coNP are closed under concatination (T).

2 26/10/09 Time and space classes, Cook Theorem.
2 29/10/09 Cook and Levin reductions (T).
3 2/11/09 NP-complete problems, 2SAT and Max-2SAT.
3 5/11/09 NP comlete Unary languages, self reductions (T)
4 9/11/09 Space Complexity (L)
4 12/11/09 Time hierarchy, the padding argument, 3NAE and 3-Colorability (T)
5 16/11/09 Space complextiy (Cont.)
5 19/11/09 2SAT is NL-complete