Computer Science
Tel-Aviv University

Computational Complexity

Spring 2008


  • [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

Some Information


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.


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


Main references:


Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak


Introduction to the Theory of Computation, by Michael Sipser (1st or 2nd edition only)


Computational Complexity, by Christos H. Papadimitriou

Other textbooks:


Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone.


Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan


Approximation Algorithms, by Vijay V. Vazirani


Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest


Attendance, homework assignments, quiz


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




Class Topics


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(n2n), but there exist functions that require circuits of size at least 2n/10n [AB6, S9.3, P4.3].


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].


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; Σ2P, Π2P; the polynomial-time hierarchy [AB5.1].


May 20

NP and coNP; The classes P, NP and coNP are closed under the Kleene star.


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 PA = NPA and oracle A such that PA ≠ NPA) [AB3.5].


May 27

MINIMUM-CIRCUIT is in Π2P [P 17.2]; Σ2P = NPSAT [AB5.5]; At least one of P=NP and NP=EXP is false.


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].


June 2,10

Logspace Reductions, Composition in [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.


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].


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 Rn (informal).


June 24

Gap problems; Hardness of Gap-Problems implies Hardness of approximation. Applied to E4SAT.


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|2) minimum cuts.


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 Σ2P [AB7.7,P17.2]. (Oded Goldreich's notes)


July 8

If SAT is in BPP then NP=RP; Equivalence of two definitions of ZPP.


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.