Theory of Computing
Cornell University – Fall 2012
Computer Science 6810

Course Information

Meeting
Tuesdays and Thursdays, 1:25pm – 2:40pm, 306 Hollister Hall
Instructor
David Steurer, 4134 Upson Hall (office hours by appointment)
Teaching Assistant
Sidharth Telang (sdt45)
Piazza
piazza.com/.../cs6810 (please sign up if you are enrolled/sit in the course)

Description

This graduate course gives a broad introduction to complexity theory, including classical results and recent developments. Complexity theory aims to understand the power of efficient computation (when computational resources like time and space are limited). Many compelling conceptual questions arise in this context. Some examples: Most of these questions are (surprisingly?) difficult and far from being resolved. Nevertheless, a lot of progress has been made toward understanding them (and also why they are difficult). We will learn about these advances in this course. A theme will be combinatorial constructions with random-like properties, e.g., expander graphs and error-correcting codes.

Prerequisites

The course has no formal prerequisites, but it assumes the following skills:
Mathematical maturity
comfort with mathematical proofs, discrete structures (e.g., graphs), basic linear algebra (e.g., eigenvalues), basic probability theory (e.g., Chernoff bounds)
Algorithmic thinking
familiarity with mathematical models of computation (e.g., Turing machines), basic algorithms (e.g., connectivity in graphs)

Grading

Grades are based on the following components:

Topics

Tentative list of topics
Basic resources
time-/space-bounded Turing machines, depth-/size-bounded circuits
efficient universal simulation
P vs. NP
reductions, completeness, alternation
Diagonalization
hierarchy theorems, intermediate problems
limits of diagonalization/relativization
Probabilistic computation
randomness vs alternation
random walks in graphs, eigenvalues, expansion
undirected connectivity in randomized logspace
randomness-efficient error reduction
Interaction
graph isomorphism, polynomial space vs. interactive proofs
Cryptography
computational security, one-way functions, zero-knowledge proofs
Approximation
hardness of approximation vs. probabilistically checkable proofs (PCPs)
combinatorial proof of the PCP theorem
Fourier analysis over Boolean hypercubes, optimal 3-bit PCP
parallel repetition theorems
Unique Games Conjecture
Derandomization
undirected connectivity in deterministic logspace
pseudorandom generators from hard functions
worst-case to average-case reduction
Communication Complexity
lower bound for set disjointness via information theory
applications to lower bounds for linear programs
Proof Complexity
resolution lower bound for random 3CNF formulas
lower bounds for semidefinite programming hierarchies
Quantum Computation
general search, integer factorization
Natural Proofs

August
Su Mo Tu We Th Fr Sa
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
September
Su Mo Tu We Th Fr Sa
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
October
Su Mo Tu We Th Fr Sa
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
November
Su Mo Tu We Th Fr Sa
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1

Lectures


Homework

You can collaborate in (disjoint) groups of up to three people. However, you need to submit homework individually (written by yourself, in your own words). Your submission should acknowledge all members of your group.

Please use LaTeX to write your homework. (You can start from the source file of the homework assignment. To compile those, you need the file macros.tex)


References

Books

Our main reference is Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak. Drafts of all chapters are available online.

Other books on complexity theory:

Courses

Boaz Barak
Computational Complexity, Spring 2009
Rafael Pass
Theory of Compting, Spring 2009
Sanjeev Arora
Computational Complexity Theory, Spring 2003
Madhu Sudan
Advanced Complexity Theory, Spring 2009
Luca Trevisan
Computational Complexity, Spring 2008
Venkatesan Guruswami & Ryan O'Donnell
An Intensive Introduction to Computational Complexity Theory, Spring 2009