Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2007

Announcements

Moed b:

The grades will be published by tomorrow (Sep 5th).
The moed b exam and its solutions are available in the Previous exams file.
The point ditribution is as follows:
1a 25; 2a 9; 2b 8; 2c 8; 2d 8; 3a 9; 3b 8; 3c 8; 4a 10; 4b 10; 4c 5;
Special marks on your exam form:
e: empty answer, therefore 15% of the points.
A factor of +10 points was given.

Homework assignments

Instructions and exercises

Out	Due	Questions
Jun 21	End of Term	1. Prove that PCP1/2,1[lg n, lg n] is in NP. 2. Solve Q15 from [AB 2.7] regarding max-cut. You may allow multi-graphs (i.e, parallel edges are allowed). Hint: start from 3NAE,with a triangle for evey clause, and parallel edges between a vartex of a variable and its negation.
Jun 12	Jun 26	Problem set 3: 3 Problem set 5: 5,6 Problem set 6: 3, 4a Problem set 8: 2
May 29	12 Jun	Problem set 3: 1,2 Problem set 4: 4,6 Problem set 5: 4
Mar 20	Apr 10	Problem set 5: 2 Problem set 10: 1, and 3 (prove SAT<p HALT instead of SAT <L HALT) Problem set 8: 1 (without assuming 11:1). Problem set 11: 1
Mar 6	Mar 20	Show that if L can be decided by a machine M then L can also be decided by a machine M' with working alphabet set of size at most 4, such that the running time of M' is at most c times the running time of M (where c is a constant, which may depend on M).
Feb 28	Mar 13	Problem set 1: 1a, 1b except the first and the last, 2. Problem set 2: 4, 5.

Some Information

Lectures

Group 1: Monday 10:00-13:00, Orenstein 103
Group 2: Thursday 09:00-12:00, Dan David 001
Recitations: Tuesday 15:00-16:00 Schreiber 006,
16:00-17:00, 17:00-18:00, 18:00-19:00 Schreiber 008.

Instructors

Lecture notes on the web

Previous courses in TAU by Muli Safra, Amnon Ta-Shma
Steven Rudich from CMU
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	Feb 26, Mar 1	Administration; Historical remarks; Computability [AB1, S part II]: languages, the Turing machine model of computation and its robustness, the universal turing machine, uncomputable functions; Time complexity [AB2,S7]: the class P
	Feb 27	Administration; Reciting O notations [AB1 or CLR]; Multi-vs-single tape TM - to be continued [P2.3 or S3.2].
2	Mar 5, Mar 8	The class NP, problems in NP, alternative definitions of NP, reductions and NP-completeness, TMSAT is NP-complete [AB2]; The Cook-Leving theorem [S7.4]
	Mar 6	Multi-vs-single tape TM [P2.3 or S3.2].
3	Mar 12, Mar 15	Rest of Cook-Levin; more NP-complete problems: 3SAT, E3SAT, IntegerProgamming, IndependentSet, Clique, VertexCover [AB2.4]; how to deal with NP-complete problems; Decision vs. Search [AB2.5]; what if P=NP?; More complexity classes: coNP [AB2.6]
	Mar 13	Strike
4	Mar 19, Mar 22	EXP, NEXP; Σ₂^P, Π₂^P; the polynomial hierarchy [AB5.1]; the time hierarchy theorem [AB3.1]; oracle machines and the limits of diagonalization (oracle A such that P^A = NP^A) [AB3.5]
	Mar 20	4NAE and 3NAE are NPC [PAP 9.2]. 3Col is NPC [PAP 9.3] (to be continued).
5	Mar 26, May 24	Oracle A such that P^A ≠ NP^A; Space complexity [AB4,S8]; PSPACE, NPSPACE, L, NL; PATH in NL; Savitch's theorem [AB4.3,S8.1]; TQBF is in PSPACE
	Mar 27	3Col is NPC [P 9.3], Composition in L [AB4 or Sip 8.1].
6	May 28, May 31	TQBF is PSPACE-complete; NL-completeness [AB4.4]; NL=coNL [AB4.4.2]
	May 29	st-Directed Hamilton Path is NPC [AB2.4 or Sip 7.35].
7	Jun 4, Jun 7	What we did so far and what are we going to do next. Randomized computation; checking AB=C, Schwartz-Zippel [AB7]
	Jun 5	Reciting NL-hardness and Immerman Theorem
	Jun 8 A	Chernoff [AB 7.4] , RP [AB 7.3 PAP 11].
	Jun 8 B	Approximation Algorithms: Vertex Cover [P 13.1], Set Cover [V2,2.1].
8	Jun 11, Jun 14	Approximation algorithms, The PCP Theorem, Hardness of approximation [V2 AB18-18.2]
	Jun 12	Gap problems,Hardness of Gap-Problems implies Hardness of approximation. [AB 18.2] Applied to 4NAE [P 9.2].
9	Jun 18, Jun 21	Average Case Complexity [AB15-15.1 P page 383]
	Jun 19	Gap preserving properties of the reduction to Max2Sat.
10	Jun 25 Jun 28	OWF [AB 10.1] Discrete Log and El-Gamal [MOV 8.9.1].
	Jun 26	PCP vs. Gap-problems [AB18].

Computer Science Tel-Aviv University

0368.3168 Computational Complexity