Computer Science

Computational Complexity Theory
0368.3168.07

Spring 2013

Lectures

Tuesday 10:0013:00,
Dan David 1 
Instructor

Amnon TaShma  Schreiber 127  6405364 
T.A 
·
Michal Kleinbort.
Office hour: Wednesday, 15:0016:00. Please email if you plan to come. ·
Itay
Berman. Office hour: Tuesday, 17:0018:00. Please email if you plan to
come. 
· Homework submission is mandatory. However, you can submit an empty page
(with your id only).
· The
final grade is not affected by the homework grade.
· Submit Homeworks to the wooden box titled
"Complexity" (number 5) near Shreiber
004005.
· Collect graded homeworks from the copy room.
· To appeal, write your arguments and submit it together with the
original homework, same as you submit homeworks.
· Answered appeals can be collected from the copy room as well.
· Homework submission list
(for exercises 14)
Textbooks

Main references:
Other textbooks:


Previous Exams 
Previous exams 

Other links 
A compendium of
NPcomplete problems and what's known about them. 
Date 
Class Topic 
Notes 
Recitation Topic 
Notes 
1. Feb 26 
· Administration; · Turing machine model of computation [AB
1]; · Time hierarchy theorem [AB 3.1]; · Circuits [AB 6.1] 

·
Simulating Mulitape Turing machine by
a single tape Turing machine with quadratic time overhead. 

2. Mar 5 
·
Oracle machines [AB 3.5].
·
Space complexity [AB 4, S 8]; ·
L, PSPACE. ·
stCON is space(log^2n) [AB 4.2.1];

· The padding argument 

3. Mar 12 
·
Logspace Reductions, Composition in L [AB 4, S 8.1]; · CVAL is Pcomplete under logspace
reductions [6.7.2] 
· Same as lecture 2 
· Boolean Circuits 

4. Mar 19 
·
TQBF is PSPACEcomplete [AB 4.2] ·
2 definitions of NP [AB 2.1] 
· TQBF is PSPACEcomplete 

5. Apr 9 
· SAT, 3SAT [AB 2.3], 3NAE [P 9.2], 3COL [P
Thm 9.8] · Search to decision reduction for SAT [AB
2.5] · coNP [AB 2.6] · The Languages Σ_{1}SAT,
Π_{1}SAT
[AB 5.2] 
· NP and P are closed under * · NPC and Unary Languages 

6. Apr 23 
· The polynomial time hierarchy [AB 5.2] 
· SubsetSum is NPComplete. 

7. Apr 30 
· Nondeterministic space [AB 4.1] · Savitch [AB 4.2] · Immerman [AB 4.3] 
· Same as lecture 6 
· 2 Definitions of NL. · Savitch, Immerman 

8. May 7 
· Randomized computation.[AB 7.1] · RP [AB 7.3], BPP [AB 7.1] · RP in NP [AB 7.3] · Verifying matrix multiplication [MR 7.1] · A randomized algorithm for Perfect Matching [MR 7.3] 
· Amplifications of
BPP. 

May 10 
· Quiz (1 hour, starting at 9:00) 

9. May 21 
·
Randomized communication complexity of the equality function [AB EX.
13.15, AB p.130] · Sipser's theorem [AB 7.5] 
· Karger's
algorithm for mincut 

10. May 28 
· Approximation algorithms · Approximating VC (with maximal matching) · Approximating SetCover with
the greedy algorithm (unit weights)
[V 2.1] · Optimization problems and integer programming · Linear programming (LP), relaxations and rounding [V
13.1, 14.1, 14.2] · Approximating SetCover with
a bounded number of occurrences of each item – with LP · Approximating the general SetCover
problem  with LP · Goemans
Williamson MaxCut approximation (Not part of the
exam material!) 
· Sipser's theorem. · BPP is in P/poly. 

11. Jun 4 
·
Promise problems. ·
Gap problems. ·
GapMax3SAT is NPhard. [AB 11.2] ·
NP hardness of gap problems vs.
NPhardness of ·
Gap preserving reductions. ·
Gap MaxClique, GapMaxIS
[AB 11.4] 
· Approximating Weighted Set Cover 

12. Jun 11 
· Gap minVC. [AB 11.4] · The importance of location of the gap. · Gap Max 3SAT[b] is NPhard for some constant b. [V 29.4] 
·
MAX2SAT is hard to
approximate for some constant factor. 

13. Jun 18 
· The PCP theorem. [AB 11.2] · GNISO has a long PCP system with only one query bit [AB 11.2.1]. · CSP [AB 11.3.1]. · Two equivalent views of the PCP theorem [AB 11.3]. 
·
Constraint Satisfaction Problems 