
Computer
Science 522
Advanced Complexity Theory
Sanjeev
Arora

Spring
2014

Directory
General Information  Assignments
 Handouts
 Interesting
Links
Course Summary
The course starts by laying the basic framework and results
of computational complexity theory and then studies in detail some
of the achievements of the past two decades, such as:
 approaches to the famous P vs NP question, an understanding
of why they are stuck, and ideas for making future
progress
 new probabilistic deﬁnitions of classical complexity classes
(IP = PSPACE and the PCP Theorems) and their implications for
the hardness of computing approximate solutions to ﬁeld of
approximation algorithms;
 a theory of derandomization and pseudorandomness based upon
computational hardness; beautiful constructions of pseudorandom
objects such as extractors and expanders, and their uses in
complexity theory
 Shor's algorithm to factor integers using a quantum
computer;
 Frontier of our knowledge wrt P vs NP question.
Towards the end we will put draw upon the expertise we have built
up over the term to understand recent results such as Ryan
Williams' 2011 result separating NEXP from ACC0.
Prerequisites: COS 340/341 or equivalent math background
(basically, ability to do math proofs). Some exposure to theory of
computation at an undergrad level is recommended, though not
essential (those who lack such a course should do selfstudy using
Sipser's Theory of Computation or an equivalent text.)
Interested undergrads should contact the instructor. Undergrads
and grads will be graded separately.
About this course
Text:
Computational
Complexity:
A
Modern
Approach by Arora and Barak. Required. Try to get the latest
printing (Jan 2011); it corrects many typos from earlier
printings.
Grading: 60% of the grade will be based upon
assignments, which will be handed out every two weeks. 40% will
be based upon a long takehome final (open book).
Every student taking the course will have the responsibility to
grade the homework once during the term, under my supervision.
There might also be a small course project at the end of the
semester.
Administrative Information
Lectures: TuesThurs 34:20pm, Room: 302
Coffee halfhour after class on Thurs (optional).
Professor: Sanjeev Arora
 307 CS Building  2583869 arora@cs.princeton.edu
Office hrs: Tue 23pm, or by appointment. (Or try dropping
by any afternoon.)
ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD
ACROBAT READER HERE.
Lecture notes and Readings
 Lecture 1 (Feb 4) The Turing
Machine model. P, NP, NPcompleteness. Chapter 1.
 Lecture 2 (Feb 6) NPcompleteness, meaning of P vs NP.
Introduction to Polynomial Hierarchy. Chapter 2.
 Lecture 3 (Feb 11; lecturer Zeev Dvir) Polynomialhierarchy
and alternation. Introduction to circuits. Chapter 5. (Just
read up to Section 5.2 in Chapter 5 for now.)
 Lecture 4. (Feb 13) Diagonalization. Chapter 3. (Section 3.3
is optional, though recommended.)
 Lecture 5 (Feb 18) Space Bounded Computation and Space
complexity. Chapter 4.
 Lecture 6 (Feb 20) NL =coNL. Karp Lipton Theorem.
 Lecture 7 (Feb 25) Randomized computation. (Chapter 7).
 Lecture 8 (Feb 27) Finish randomized computation. Odds and
ends that we missed in Chapters 17 including Timespace
tradeoff for SAT, smalldepth circuits (NC) etc.
 Lecture 9 (Mar 4) Interactive proofs. Variants, private vs
public coins. Interactive proof for #SAT.
 Lecture 10 (Mar 6) IP=PSPACE, program checking, testing,
random selfreducibility etc... (Chapter 8 finished.)
 Lecture 11 (Mar 11) Start Quantum computation. Quantum
reality. Nonlocal games ( CHSH). Quantum circuits and BQP.
Classical computation is a subcase. Additional reading:
Lecture
notes by John Watrous on Nonlocal games.
 Lecture 12 (Mar 13) Quantum fourier transform, and Shor's
algorithm. (Finishes Chapter 10 except for Grover's algorithm,
which is optional reading.)
 Lecture 13 (Mar 25) Strongly hard functions and
Derandomization via NisanWigderson generator. (Chapter 20,
Sections 20.1, 20.2. Useful reading: Yao's hybrid argument in
Section 9.3.)
 Lecture 14 (Mar 27) Amplification of hardness via Yao's XOR
Lemma. (Chapter 19, Section 19.1. Also did a survey of other
sections in Chapter 19 but may return to them later.)
 Lecture 15, 16, 17 (April 1 8) Circuit lowerbounds. Guest
lecturer Avi Wigderson. (Chapter 14)
Honor Code for this
class
Collaborating with your classmates
on assignments is encouraged (and may be essential to get the
most out of the course). You must, however, list your
collaborators for each problem. The assignment questions have
been carefully selected for their pedagogical value and may be
similar to questions on problem sets from past offerings of
this course or courses at other universities. Using any
preexisting solutions from these or any other sources is strictly
prohibited.