­­­­­­­­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

 

http://rjlipton.files.wordpress.com/2010/11/zoo.png

 

Text Book:

Sanjeev Arora and Boaz Barak, Computational Complexity – A Modern Approach, Cambridge University Press, 2009.

 

Lectures: (with scribe notes by students; please use caution when using the lecture notes!)

 

 

Date

Topic

Reading

Psets

1

Thursday,

September 6

The polynomial hierarchy and time-space lower bounds

Chapter 5.4

 

 

2

Tuesday,

September 11

(Patriot Day)

Relativization and its limits; Baker-Gill-Solovay

 

Chapters 3.1- 3.4

 

 

Pset 1 out

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

AC0 and switching lemma

 

Chapter 14.1

 

5

Thursday, September 20

Razborov’s monotone lower bound

 

Chapter 14.3

Pset 1 due

6

Tuesday,

September 25,

Natural Proofs

Chapter 23

7

Thursday,

September 27,

The frontiers of circuits lower bounds; MAEXP lower bound; rigidity;

Chapter 14.4

Pset 2 out

8

Tuesday,

October 2,

Communication complexity (guest lecture by Boaz Barak)

Chapter 13

Information Theory - read for Thursday

 

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)

Avi’s article

11

Tuesday, October 16

Randomized algorithm for undirected connectivity, random walks and linear algebra techniques

Chapter 21.1

Pset 3 out

12

Thursday, October 18

Expanders, SL=L

Chapter 21.4

 

Tuesday, October 23

FOCS’12

 

13

Thursday, October 25

Pseudorandom generators (guest lecture by Madhu Sudan)

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

Derandomization requires circuit lower bounds

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

Pset 4 out

18

Tuesday, November 13

Powering

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

Analysis of long code test via Fourier analysis

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

Unique SAT, parity SAT, approximate counting

Chapters 17.4.1-17.4.4

Pset 5 out

23

Tuesday, December 4

Toda’s Theorem

Chapter 17.4.5

 

24

Thursday, December 6

Characterization of ACC0, Non-trivial SAT algorithm for ACC0

Web addendum

Pset 5 due

25

Tuesday, December 11

ACC0 vs. NEXP – from SAT algorithms to lower bounds

Web addendum

 

 

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:

 

Lecture notes template

 

The Zoo:

 

Complexity 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.

 

Sample Past Offerings: (the current offering is updated, and does not mirror past offerings exactly)

·  Spring 2002

·  Spring 2003

·  Spring 2005

·  Spring 2007

·  Spring 2011