Computer Science
Tel-Aviv University

Computational Complexity

Spring 2007


Moed b:

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


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.

Oded Regev | Schreiber 103 | 6407996 | Office hour: Monday 13:00
Amnon Ta-Shma | Schreiber 127 | 6405364
T.A.: Oded Schwartz | Schreiber Open Space | 6405398 | Office hour: Tuesday 19:10
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)

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
Attendance, homework assignments
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


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; Σ2P, Π2P; the polynomial hierarchy [AB5.1]; the time hierarchy theorem [AB3.1]; oracle machines and the limits of diagonalization (oracle A such that PA = NPA) [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 PA ≠ NPA; 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].