CSE 582 Computational Complexity, Fall 2014

Tuesday and Thursday, 5:30-7:00 PM, Bryan 509C.

After Hours Office Door Policy

509C is located inside the CSE main office, Bryan 509. As our class is after hours for the office, the door is required to be shut once we start lecture. Please make an effort to be on time!

Instructor

Brendan Juba
Office Hours:   Wednesday 5-6 PM, Bryan 522
Email:   first initial last name at wustl

Description

An introduction to the quantitative theory of computation with limited resources. The course examines the relative power of limited amounts of basic computational resources, such as time, memory, circuit size, and random bits, as well as parallel, nondeterministic, alternating, and interactive machine models. Models that capture special kinds of computational problems, such as counting problems or approximate solutions, will also be introduced and related to the standard models. This examination will emphasize surprising relationships between seemingly disparate resources and kinds of computational problems. The course will also discuss some meta-theory, illuminating the weaknesses of standard mathematical techniques of the field against its notorious open conjectures.

Pre-requisites

Formally, CSE 241. Informally and more substantially, this class will demand "mathematical maturity." This means that you should be comfortable reading and producing mathematical arguments, i.e., "proofs." A key part of this course will be coming up with and clearly presenting such proofs on the homework.

Textbook

I recommend Computational Complexity: A Modern Approach by Arora and Barak as a reference and I will indicate which sections of the book are covered in lecture on the calendar. Moreover, the book may provide hints on some of the homework problems. It will be possible to complete the course without a copy of the book, however.

Homework, Exams, Projects, and Grading

There will be six homework assignments and a final project. The homeworks will be worth 40% of the grade and the final project will be worth 60%.

Course Website

An up-to-date version of this document appears on the web at http://www.cse.wustl.edu/~bjuba/cse582/f14.

Calendar

The schedule of lecture topics and assignments may be subject to change as the semester progresses.
MondayTuesday WednesdayThursday Friday
Aug 25
Aug 26

L1:  Modeling Computation
AB 1.1-1.3;1.6
Aug 27
Aug 28

L2:  Basic Complexity Theory
AB 1.4, 1.5, 3.1, 4.1
Assigned:  Homework 1
Aug 29
Sept 01

Holiday
Sept 02

L3:  Basic Circuit Complexity
AB 6.1-6.3, 6.5, 6.6
Sept 03
Sept 04

L4:  Nonuniform Complexity
finish AB 6.1-6.3; 14.4.4
Due:  Homework 1
Assigned:  Homework 2
Sept 05
Sept 08
Sept 09

L5:  Barrington's Theorem; Circuit Depth
Jukna 15.1, 15.4; AB 6.7.1
Sept 10
Sept 11

L6:  Circuit Lower Bounds I: random restrictions
Jukna 12.3 (AB 14.1)
Sept 12
Sept 15
Sept 16

L7:  Circuit Lower Bounds II: switching lemma, polynomial approximations
AB 14.1.2, start 14.2
Sept 17
Sept 18

L8:  Circuit Lower Bounds III: Razborov-Smolensky, ACC0 and TC0
finish AB 14.2 (Jukna 12.5-12.6, p.346)
Due:  Homework 2
Assigned:  Homework 3
Sept 19
Sept 22
Sept 23

L9:  Randomized Complexity
AB 7.1, 7.2.3, 7.3, 7.4.1, 7.5.1, 20.1
Sept 24
Sept 25

L10:  Pseudorandom Generators
AB 20.1.1, 21.6
Sept 26
Sept 29
Sept 30

L11:  Hardness vs. Randomness
AB 9.3.1, 20.1.2, 20.2, intro. of 19.4
Oct 01
Oct 02

L12:  Application: Cryptography
AB 9.1, 9.2.1-9.2.3, 9.5.1
Due:  Homework 3
Assigned:  Homework 4
Oct 03
Oct 06
Oct 07

L13:  Reductions and Completeness
AB 2.2, 4.3, 6.7.2
Oct 08
Oct 09

L14:  NP
AB 2.1, 2.3 (6.1.2), 2.7.1-2.7.3, 2.7.5
Oct 10
Oct 13
Oct 14

L15:  Ubiquity of NP-completeness
AB 2.4, 3.3
Oct 15
Oct 16

L16:  Nondeterministic Space
AB 2.1.2, 4.2.1 (start 4.2), 4.3
Due:  Homework 4
Assigned:  Homework 5
Oct 17 Holiday
Oct 20
Oct 21

L17:  Co-Nondeterminism
AB 2.6.1, 4.2, start 4.3.2
Oct 22
Oct 23

L18:  Immerman-Szelepcsenyi; Alternation I
AB 4.3.2, 5.1, 5.3, start 5.2
Oct 24
Oct 27
Oct 28

L19:  Alternation II; Relativization Barrier
AB 5.2.1, 5.2.2, 5.5, 3.4
Oct 29
Oct 30

L20:  Natural Proofs Barrier
finish AB 3.4, AB 6.4, 23.1, 23.2-23.2.1
Due:  Homework 5
Assigned:  Homework 6
Oct 31
Nov 03
Nov 04

L21:  Counting and Sampling
AB 23.2.2-23.2.3, 23.3, 17.1, 17.2, 17.3
Nov 05
Nov 06

L22:  Toda's Theorem
AB 17.3.2, 17.4
Nov 07
Nov 10
Nov 11

L23:  Interaction
finish AB 17.4.4, AB 8.1, 8.2-8.2.2
Nov 12
Nov 13

L24:  IP = PSPACE
AB 8.2.4 (+7.5.2), 8.3-8.3.2
Due:  Homework 6
Nov 14
Nov 17
Nov 18

L25:  PCP I
AB 8.3.3, 8.5, 11.1, 11.2, 11.4
Nov 19
Nov 20

L26:  PCP II
AB 11.3, 11.5
Nov 21
Nov 24
Nov 25

Thanksgiving travel day
Nov 26
Nov 27

Thanksgiving
Nov 28
Dec 01
Dec 02

L27: PCP III
AB 22.1, 22.2
Dec 03
Dec 04

Final Project Presentations
Due:  Final Project Write-up
Dec 05