6.841J/18.405J Advanced Complexity
Theory
Fall 2012 | TR2:30-4, 4-153 | 3-0-9 H Level Grad Credit | Course Info
Instructor: Dana Moshkovitz
TA: Henry Yuen
Text Book:
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; Baker-Gill-Solovay |
Chapters 3.1- 3.4 |
|
|
3 |
Thursday,
September 13 |
Boolean circuits, simple circuit lower bound, uniformity
vs. non-uniformity (Karp-Lipton) |
Chapters
6.1-6.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 1-190) |
||
|
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.1-20.2 |
Pset
3 due |
|
|
14 |
Tuesday,
October 30 |
From
worst-case hardness to average-case hardness (guest lecture by Madhu Sudan) |
Chapter 19 |
|
|
15 |
Thursday,
November 1 |
Chapter
20.4 |
|
|
|
16 |
Tuesday,
November 6 |
PCP,
2-prover games and hardness of approximation (guest lecture by Prasad
Raghavendra) |
Chapters 11.1-11.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; Label-Cover, parallel repetition, |
Chapters 22.4,22.9.3-22.9.5 |
|
|
22 |
Thursday,
November 29 |
Chapters
17.4.1-17.4.4 |
||
|
23 |
Tuesday,
December 4 |
Chapter 17.4.5 |
|
|
|
24 |
Thursday,
December 6 |
Characterization
of ACC0, Non-trivial SAT algorithm for ACC0 |
Pset
5 due |
|
|
25 |
Tuesday,
December 11 |
ACC0 vs. NEXP – from SAT
algorithms to lower bounds |
|
Mailing List:
Subscribe to get lecture announcements.
Questions & Answers:
·
Piazza
for discussions about 6.841: https://piazza.com/class#fall2012/6841j18405j
· CS Stack Exchange for general questions regarding complexity theory: http://cstheory.stackexchange.com/
Lecture Notes Template:
The Zoo:
Pre-req:
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.1-7.4 (Randomized computation) of the Arora-Barak 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.