**Computational Complexity**

**16:198:538
Fall 2013**

**Instructor:**
Shubhangi Saraf

**Email:** shubhangi.saraf@rutgers.edu

**Timing: **Mon 12
pm – 3 pm

**Location: **HILL 005

**Office hours: **Mon 3pm – 4 pm (Hill 426)

**Description:** This course will serve as a graduate
course in complexity theory.

Computational complexity is the study
of what computational tasks can be achieved efficiently, or with limited
computational resources. Though computer scientists and mathematicians have intensively
studied this topic in the last several decades, we still understand very little
about computational efficiency. Although
there have been some remarkable results giving some answers and insights into
some of the questions, most of major questions are still unanswered. Indeed it
seems almost shocking that we still don't know the answers to them. In this
course we will cover classical results as well as more recent results leading
up to the state of the art in the field. Along the way we will encounter many
surprising connections, beautiful mathematics, and a host of intriguing
questions.

**Recommended Text:** "Computational Complexity: A Modern
Approach" by Arora and Barak.

**Also available online :**

**Another great book (also
available online): **

"Computational
Complexity: A conceptual Perspective" by Oded Goldreich

**Prerequisites: **It will be helpful to
have some background in algorithms/discrete math, but no formal prerequisite
will be enforced. If you do not satisfy the official prerequisites but are
still interested in registering for the course, and you are concerned if you
will be sufficiently prepared for the course, send an email to __shubhangi.saraf@rutgers.edu
__

The only real prerequisite is some
mathematical maturity.

**Homework/grading:** There will be 3 problem sets. Students will also be required to
scribe one (or possibly more) lecture.

**Latex template for scribe notes:
**Here is the sample file, and the preamble file
that goes along with it

**Homework 1 (due October
7)**

**Homework 2 (due November
4)**

**Homework 3 (due December
2)**

**Schedule:**

§
**Lecture 1
(09/09): **Administrative details, course overview, Turing machines,
complexity classes. **NOTES**

§
**Lecture 2
(16/09): **NP-completeness, Cook-Levin Theorem, Hierarchy theorems. **NOTES**

§
**Lecture 3
(23/09): ** Hierarchy Theorems,
Ladner’s theorem, Oracles and relativization, space
complexity **NOTES**

§
**Lecture 4
(30/09): ** PSPACE completeness, Savitch’s theorem, L, NL **NOTES**

§
**Lecture 5
(07/10): ** NL = co-NL, Alternations,
Polynomial hierarchy **NOTES**

§
**Lecture 6
(14/10): ** TIME-SPACE tradeoffs,
Boolean circuit complexity. **NOTES**

§
**Lecture 7
(21/10): ** Karp-Lipton Thm, Randomized complexity, BPP in P/poly. **NOTES**

§
**Lecture 8
(28/10): ** BPP in PH (Sipser Lautemann), Interactive
proofs. **NOTES**

§
**Lecture 9
(04/11): ** AM proofs, Goldwasser-Sipser, Co-NP in IP. **NOTES**

§
**Lecture
10 (11/11): ** #SAT in IP, IP in
PSPACE, PCP theorem. **NOTES**

§
**Lecture
11 (18/11): ** PCP theorem and hardness
of approximation, Local testing, local decoding **NOTES**

§
**Lecture
12 (25/11): ** Linearity Testing (BLR),
exponential length PCP for SAT **NOTES**

§
**Lecture
13 (02/12): ** Proof of PCP theorem (by
Dinur)

§
**Lecture
14 (09/12): ** Cancelled. Make up class on Cryptography held on
(19/11)

**Tentative (and partial) list of topics:**

· Hierarchy theorems, Diagonalization, Relativization,

· Alternations, NP completeness,

· Space bounded computation, sublinear space algorithms

· Randomness in computation, BPP, RP

· Interactive proofs

· Circuit lower bounds

· Hardness versus randomness – derandomization, pseudorandom generators

· PCP theorem, hardness of approximation