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