Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2009

Announcements

The exams and the final grades of Moed B were submitted to the secretariat. The exam can be found in the exam file below.
The exams and the final grades were submitted to the secretariat. In general, the final grade is 0.85*EXAM+0.15*QUIZ, but in order to pass the course you must pass the exam. For multiple-choice question 8 in version 1 (which is question 4 in version 2), students who chose the answer b (instead of the correct answer f) got 4 points out of 6.
The exam can be found in the exam file below.
The quiz and its solutions are in the exam file below.

The mid-term exam will be at 9:00 on May 8.
The material for the mid-term exam includes the first five lectures, the first five recitations and the first four homework sheets (i.e., what we did until April 21).
Added lecture notes on time complexity
The mid-term exam is rescheduled to May 8.
Google group for our course is available here.

Homework assignments

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

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 Σ₂^P, Π₂^P [AB5.1] If P=NP then P=Σ₂^P The time hierarchy theorem [AB3.1] Oracle machines and the limits of diagonalization (oracle A such that P^A = NP^A and oracle A such that P^A ≠ NP^A) [AB3.5]
	Mar 31	P^P is equal to P, but EXP^EXP is not equal to EXP An example for a language in Pi₂^P
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

Computer Science Tel-Aviv University

0368.3168 Computational Complexity