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:
- Is finding a solution inherently more difficult than verifying it?
- Do more computational resources mean more computing power?
- Is it easier to find approximate solutions than exact ones?
- Are randomized algorithms more powerful than deterministic ones?
- Is it easier to solve problems in the average case than in the worst case?
- Are quantum computers more powerful than classical ones?
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:
-
Homework
(weekly)
-
Scribe notes
(at least once)
-
Project
(at the end of the semester)
-
Participation
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)
-
Homework 1 (due Friday, August 31)
PDF
TEX
-
Homework 2 (due Friday, September 7)
PDF
TEX
-
Homework 3 (due Friday, September 14)
PDF
TEX
-
Homework 4 (due Saturday, September 22)
PDF
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:
- Computational Complexity: A Conceptual Approach by Oded Goldreich
- Theory of Computation by Dexter Kozen
- Computational Complexity by Christos Papadimitriou
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