Advanced Complexity Theory
General Information | Assignments
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
- 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
- a theory of derandomization and pseudorandomness based upon
computational hardness; beautiful constructions of pseudorandom
objects such as extractors and expanders, and their uses in
- Shor's algorithm to factor integers using a quantum
- 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 self-study 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
by Arora and Barak. Required. Try to get the latest
printing (Jan 2011); it corrects many typos from earlier
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 take-home 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
Lectures: Tues-Thurs 3-4:20pm, Room: 302
Coffee half-hour after class on Thurs (optional).
Professor: Sanjeev Arora
- 307 CS Building - 258-3869 firstname.lastname@example.org
Office hrs: Tue 2-3pm, 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, NP-completeness. Chapter 1.
- Lecture 2 (Feb 6) NP-completeness, meaning of P vs NP.
Introduction to Polynomial Hierarchy. Chapter 2.
- Lecture 3 (Feb 11; lecturer Zeev Dvir) Polynomial-hierarchy
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 1--7 including Time-space
tradeoff for SAT, small-depth 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 self-reducibility 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:
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 Nisan-Wigderson generator. (Chapter 20,
Sections 20.1, 20.2. Useful reading: Yao's hybrid argument in
- 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
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