
0368.3168

Spring 2008 
Lectures 
Group 1: Monday 10:0013:00, Orenstein 103 

Instructors 
Oded Regev 
Schreiber 103  6407996 

Lecture notes on the web 
Previous courses in TAU by Muli Safra,
Amnon TaShma 

Textbooks 
Main references:
Other textbooks:


Requirements 
Attendance, homework assignments, quiz 

Prerequisites 
Computational models, Algorithms 

Other links 
A compendium
of NPcomplete problems and what's known about them. 
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^{n}), but there exist functions that require
circuits of size at least 2^{n}/10n [AB6, S9.3, P4.3]. 
2 
May 12,13 
The class NP, problems in NP, alternative definitions of NP,
reductions and NPcompleteness, TMSAT is NPcomplete [AB2]; The CookLevin
theorem [S7.4]. 

May 13 
If there exists a unary NPcomplete language then P=NP (Berman's
Theorem); NPcompleteness of MAXCUT (via a reduction from NAE3SAT) [P 9.3]. 
3 
May 19,20 
How to deal with NPcomplete problems; Decision vs. Search [AB2.5]; what if P=NP?;
More complexity classes: coNP [AB2.6]; EXP, NEXP; Σ_{2}^{P},
Π_{2}^{P}; the polynomialtime 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 KarpLipton
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 
MINIMUMCIRCUIT is in Π_{2}^{P} [P 17.2]; Σ_{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
PSPACEcomplete [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 NLcomplete [AB4.4]; The class ZNL; ImmermanSzelepcsényi Theorem: NL=coNL [AB4.4.2]
(to be continued). 

June 10 
Padding argument: NL ≠ DTIME(n); 2SAT is NLcomplete; Reciting ImmermanSzelepcsényi Theorem. 
7 
June 16,17 
Optimization
problems, approximation algorithms, 2approximation for Vertex Cover
(VC) via maximal matching [P13.1]. Linear
programming, Integer programming, VC ≤_{p} IP. LP is in P and IP is NPhard. Relaxations. Rounding. A
2approximation for (weighted) VC via LP relaxation. A lnnapproximation for Set Cover [V2.2.1]. 

June 17 
TSP with
triangle inequality is NPcomplete; 3/2approximation 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 MAXCUT. GoemansWilliamson
approximation algorithm for MAXCUT and its analysis. Sampling a unit vector
in R^{n} (informal). 

June 24 
Gap problems; Hardness of GapProblems implies Hardness of
approximation. Applied to E4SAT. 
9 
June 30, July 1 
Primality testing: groups and subgroups, Fermat's test, Carmichael numbers,
fast exponentiation, MillerRabin
test. 

July 1 
Randomized Algorithms: Karger's algorithm
for MINCUT [MR1.1]; Every graph has O(V^{2}) 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 Σ_{2}^{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 ElGamal [MOV8.9.1]. Summary. 

July 15 
The conditional expectation technique, applied on MAXE3SAT and
MAXCUT. 