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 randomlike properties,
e.g., expander graphs and errorcorrecting 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/spacebounded Turing machines, depth/sizebounded 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

randomnessefficient error reduction

Interaction

graph isomorphism, polynomial space vs. interactive proofs

Cryptography

computational security, oneway functions, zeroknowledge proofs

Approximation

hardness of approximation vs. probabilistically checkable proofs (PCPs)

combinatorial proof of the PCP theorem

Fourier analysis over Boolean hypercubes, optimal 3bit PCP

parallel repetition theorems

Unique Games Conjecture

Derandomization

undirected connectivity in deterministic logspace

pseudorandom generators from hard functions

worstcase to averagecase 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