Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2008

Announcements

[12/08/2008] The exams were graded and the grades will be published soon.
The exam and its solution are available in the Previous exams file.
Students that got grade in the range 52-59 and submitted good exercises passed the course.
The point distribution of each question is as follows:
Q1: a – 40%; b – 20%; c – 40%
Q2: a – 45%; b – 45%; c – 10%
Q3: a – 35%; b – 15%; c – 35%; d – 15%
Q4: a – 60%; b – 40%
[20/07/2008] We will have a pre-exam recitation on July 30 at 16:00 in Dach auditorium.
[16/07/2008] An optional exercise on OWF.
[24/06/2008] The quiz and its solutions are in the exams file below. Grades.
[17/06/2008] Homework 6: In Question 5b the word "maximal" should be "maximum".
You might prefer to wait with Question 6 until next week.
[13/06/2008] In Homework 5, Question 4, the output-tape is unnecessary. Also, in Question 5a, s(|x|) should be s(n).
[09/06/2008] The Monday group will have a quiz on June 23, and the Tuesday group will have a quiz on June 24.
[03/06/2008] Notice that Homework 5 is for two weeks. The Tuesday group might prefer to wait with exercise 7 until next week.
[20/05/2008] The Monday group has an extra class on Friday 23/05/2008 at 10:00.
[20/05/2008] Graded exercises can be taken from Schreiber, room 114.
[14/05/2008] From now on, the Tuesday lectures will take place in Orenstein 103.
[07/05/2008] In Homework 1, Question 1a (for submission) the gates can have large fan-in.
[04/05/2008] The recitation of May 6 at 18:00-19:00 is cancelled due to the Memorial Day.
Instead, a recitation will be given on May 6 at 17:00-18:00 in Physics Shenkar 104 (in addition to the recitations at 15:00 and 16:00).

Homework assignments

Homework 1 Due May 13
Homework 2 Due May 20
Homework 3 Due May 27
Homework 4 Due June 3
Homework 5 Due June 17
Homework 6 Due July 1
Homework 7 Due July 8
Homework 8 Due July 15

Some Information

Lectures

Group 1: Monday 10:00-13:00, Orenstein 103
Group 2: Tuesday 10:00-13:00, Orenstein 103
Recitations: Tuesday 15:00-16:00, 16:00-17:00 Kaplun 118, 18:00-19:00 Schreiber 008.

Instructors

Oded Regev | Schreiber 103 | 6407996
Amnon Ta-Shma | Schreiber 127 | 6405364
T.A.: Ishay Haviv

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)

Aaronson's blog

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, quiz

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	May 5,6	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.
	May 6	Circuit Complexity: The classes SIZE(T(n)) and P/poly; Every language is in SIZE(n2ⁿ), but there exist functions that require circuits of size at least 2ⁿ/10n [AB6, S9.3, P4.3].
2	May 12,13	The class NP, problems in NP, alternative definitions of NP, reductions and NP-completeness, TMSAT is NP-complete [AB2]; The Cook-Levin theorem [S7.4].
	May 13	If there exists a unary NP-complete language then P=NP (Berman's Theorem); NP-completeness of MAX-CUT (via a reduction from NAE-3SAT) [P 9.3].
3	May 19,20	How to deal with NP-complete problems; Decision vs. Search [AB2.5]; what if P=NP?; More complexity classes: coNP [AB2.6]; EXP, NEXP; Σ₂^P, Π₂^P; the polynomial-time hierarchy [AB5.1].
	May 20	NP and coNP; The classes P, NP and coNP are closed under the Kleene star.
4	May 23 (Fri), 27	The Karp-Lipton Theorem [AB6.2]; 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].
	May 27	MINIMUM-CIRCUIT is in Π₂^P [P 17.2]; Σ₂^P = NP^SAT [AB5.5]; At least one of P=NP and NP=EXP is false.
5	May 26, June 3	Space complexity [AB4,S8]; PSPACE, NPSPACE, L, NL; PATH is in NL; Savitch's theorem [AB4.3,S8.1]; TQBF is PSPACE-complete [AB4.3].
	June 3	Space Complexity: An example of a language in L; An alternative definition of NL [AB4.4.1]; 2SAT is in coNL [P9.2].
6	June 2,10	Logspace Reductions, Composition in L [AB4,S8.1]; PATH is NL-complete [AB4.4]; The class ZNL; Immerman-Szelepcsényi Theorem: NL=coNL [AB4.4.2] (to be continued).
	June 10	Padding argument: NL ≠ DTIME(n); 2SAT is NL-complete; Reciting Immerman-Szelepcsényi Theorem.
7	June 16,17	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 (weighted) VC via LP relaxation. A lnn-approximation for Set Cover [V2.2.1].
	June 17	TSP with triangle inequality is NP-complete; 3/2-approximation for TSP with triangle inequality [V3.2.2].
8	June 23,24	Quiz; Proof by the probabilistic method: Every graph has a cut of size \|E\|/2. Integer program for MAX-CUT. Goemans-Williamson approximation algorithm for MAX-CUT and its analysis. Sampling a unit vector in Rⁿ (informal).
	June 24	Gap problems; Hardness of Gap-Problems implies Hardness of approximation. Applied to E4SAT.
9	June 30, July 1	Primality testing: groups and subgroups, Fermat's test, Carmichael numbers, fast exponentiation, Miller-Rabin test.
	July 1	Randomized Algorithms: Karger's algorithm for MIN-CUT [MR1.1]; Every graph has O(\|V\|²) minimum cuts.
10	July 7,8	Probabilistic complexity classes: BPP, RP (and coRP), ZPP [AB7,P11]; Amplification of BPP using Chernoff’s inequality [AB7.4,P11.2] ; BPP is contained in P/poly [AB7.6]; BPP is contained in Σ₂^P [AB7.7,P17.2]. (Oded Goldreich's notes)
	July 8	If SAT is in BPP then NP=RP; Equivalence of two definitions of ZPP.
11	July 14,15	OWF [AB10.1] Discrete Log and El-Gamal [MOV8.9.1]. Summary.
	July 15	The conditional expectation technique, applied on MAX-E3SAT and MAX-CUT.

Computer Science Tel-Aviv University

0368.3168 Computational Complexity