Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2010

Announcements

Please join the Google group here.
The quiz will take place at April 27, 10am.
The quiz grades are here, and the quiz is here.

Presentations

Homework assignments

Out	Due	Questions
3/3	17/3	Assignment 1
17/3	8/4	Assignment 2
8/4	27/4	Assignment 3
2/5	18/5	Assignment 4
17/5	2/6	Assignment 5
31/5	15/6	Assignment 6

Some Information

Lectures

Lectures: Tuesday 10:00-13:00 , Melamed 006
Recitations: Tuesday 15:00-16:00, 16:00-17:00 Shenkar 222, 18:00-19:00 Schreiber 007

Instructors

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

About Turing Machines

Schedule

Week Topics

1
L: Turing Machines, Time hierarchy (AB Chapter 1, 3.1)

T: Reductions, 3-SAT, k-NAE and graph coloring.

2
L: Space complexity, configurations, PSPACE is contained in EXP, oracle machines, karp and cook reductions. (AB 4.1.1,4.1.2, 3.4)

T: Space hierarchy, stConn is in SPACE(log²n) (AB 4.1.3, 4.2.1)

3
L: Non-deterministic TM (two definitions and their equivalence), Cook's theorem, 3SAT and Clique are NP-Hard, Starting NDTM space mahines, stConn is NL-complete, NL is contained in P. (AB 2,4.3)

T: Decision vs. Search, padding argument, sparse languges in NP. (AB 2, 4.2.1)

4
L: Space complexity, introduction to randomized algorithms.

T: 2SAT is NL-complete.

5
L: Space complexity (cont.), PSPACE.

T: Classifying the complexity of various problems.

6
L: Randomized computation, a more formal introduction (AB 7.1,7.3,7.4)

T: Amplification in Randomized computation, if NP is contained in BPP then NP=RP (AB 7.1,7.3,7.4)

7
L:Interactive proofs, graph non-isomorphisem (AB 8.1-8.3)

T: Linearity of expectation, the conditional expectation method, k-wise independence (Alon and Spencer, The Probabilistic Method, Chapter 2 and Chapter 16)

8
L: Randomized computation, The isolating Lemma, Sipser's Thm, Valiant-Vazirani Thm.

T: Valiant-Vazirani Thm: If UP = P then RP = NP. (AB 9.3)

9
L: Approximation algorithms, Vertex cover, Set Cover, Max-Cut. (V)

T: Approximation algorithms for TSP with triangle inequality. (V)

10
L: Approx. of Max-Cut (cont.), The PCP Theorem. (AB 11)

T: Hardness of approximation using PCP.

Week	Topics
1	L: Turing Machines, Time hierarchy (AB Chapter 1, 3.1) T: Reductions, 3-SAT, k-NAE and graph coloring.
2	L: Space complexity, configurations, PSPACE is contained in EXP, oracle machines, karp and cook reductions. (AB 4.1.1,4.1.2, 3.4) T: Space hierarchy, stConn is in SPACE(log²n) (AB 4.1.3, 4.2.1)
3	L: Non-deterministic TM (two definitions and their equivalence), Cook's theorem, 3SAT and Clique are NP-Hard, Starting NDTM space mahines, stConn is NL-complete, NL is contained in P. (AB 2,4.3) T: Decision vs. Search, padding argument, sparse languges in NP. (AB 2, 4.2.1)
4	L: Space complexity, introduction to randomized algorithms. T: 2SAT is NL-complete.
5	L: Space complexity (cont.), PSPACE. T: Classifying the complexity of various problems.
6	L: Randomized computation, a more formal introduction (AB 7.1,7.3,7.4) T: Amplification in Randomized computation, if NP is contained in BPP then NP=RP (AB 7.1,7.3,7.4)
7	L:Interactive proofs, graph non-isomorphisem (AB 8.1-8.3) T: Linearity of expectation, the conditional expectation method, k-wise independence (Alon and Spencer, The Probabilistic Method, Chapter 2 and Chapter 16)
8	L: Randomized computation, The isolating Lemma, Sipser's Thm, Valiant-Vazirani Thm. T: Valiant-Vazirani Thm: If UP = P then RP = NP. (AB 9.3)
9	L: Approximation algorithms, Vertex cover, Set Cover, Max-Cut. (V) T: Approximation algorithms for TSP with triangle inequality. (V)
10	L: Approx. of Max-Cut (cont.), The PCP Theorem. (AB 11) T: Hardness of approximation using PCP.

Computer Science Tel-Aviv University

0368.3168 Computational Complexity