Fall 2012  TR2:304, 4153  309 H Level Grad Credit  Course Info
Instructor: Dana Moshkovitz
TA: Henry Yuen
Lectures: (with
scribe notes by students; please use caution when using the lecture notes!)

Date 
Topic 
Reading 
Psets 
1 
Thursday, September
6 
Chapter
5.4 


2 
Tuesday, September
11 (Patriot
Day) 
Relativization
and its limits; BakerGillSolovay 
Chapters 3.1 3.4 

3 
Thursday,
September 13 
Boolean circuits, simple circuit lower bound, uniformity
vs. nonuniformity (KarpLipton) 
Chapters
6.16.5 

4 
Tuesday,
September 18 

Chapter 14.1 

5 
Thursday,
September 20 
Razborov’s monotone lower bound 
Chapter
14.3 
Pset
1 due 
6 
Tuesday, September
25, 
Chapter 23 

7 
Thursday, September
27, 
The frontiers of circuits lower bounds; MAEXP lower bound;
rigidity; 
Chapter
14.4 

8 
Tuesday, October
2, 
Chapter 13 


9 
Thursday, October
4 
Disjointness lower bound
(guest lecture
by Boaz Barak) 
Pset
2 due 

Tuesday, October
9 
Columbus Day Vacation 


10 
Thursday,
October 11 
Introduction to randomization and derandomization (guest
lecture by Avi Wigderson at 1190) 

11 
Tuesday,
October 16 
Randomized
algorithm for undirected connectivity, random walks and linear algebra
techniques 
Chapter 21.1 

12 
Thursday,
October 18 
Chapter
21.4 


Tuesday,
October 23 


13 
Thursday,
October 25 
Chapter
20.120.2 
Pset
3 due 

14 
Tuesday,
October 30 
From
worstcase hardness to averagecase hardness (guest lecture by Madhu Sudan) 
Chapter 19 

15 
Thursday,
November 1 
Chapter
20.4 


16 
Tuesday,
November 6 
PCP,
2prover games and hardness of approximation (guest lecture by Prasad
Raghavendra) 
Chapters 11.111.3 

17 
Thursday,
November 8 
Combinatorial proof of PCP: proof overview, making the graph
into an expander 
Chapters
22.2 

18 
Tuesday,
November 13 
Chapters 22.2 

19 
Thursday,
November 15 
alphabet reduction via composition, long code, long code
test 
Chapter
22.6 
Pset
4 due 
20 
Tuesday,
November 20 
Chapter 22.5 


Thursday,
November 22 
Thanksgiving 


21 
Tuesday,
November 27 
Optimal hardness of
approximation; LabelCover, parallel repetition, 
Chapters 22.4,22.9.322.9.5 

22 
Thursday,
November 29 
Chapters
17.4.117.4.4 

23 
Tuesday,
December 4 
Chapter 17.4.5 


24 
Thursday,
December 6 
Characterization
of ACC0, Nontrivial SAT algorithm for ACC0 
Pset
5 due 

25 
Tuesday,
December 11 
ACC0 vs. NEXP – from SAT
algorithms to lower bounds 

Subscribe to get lecture announcements.
· CS Stack Exchange for general questions regarding complexity theory: http://cstheory.stackexchange.com/
Lecture Notes Template:
6.840J/18.404J Theory of Computation
In particular, we’ll assume familiarity with Chapters 1 (Basic Complexity Classes), 2 (NP and NP Completeness) and 7.17.4 (Randomized computation) of the AroraBarak book. Chapters 3 (Diagonalization) and 4 (Space Complexity), as well as the beginning of Chapter 8 (Interactive Proofs) are also covered in the previous course.
Students who took 6.045 are also welcome, however 6.841J will require substantial mathematical maturity.