**Computational Complexity**

**16:198:538
Fall 2019**

**Instructor:** Shubhangi Saraf

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

**Timing: **Wednesday
1:40 pm – 4:40 pm

**Location: **1:40 pm – 3 pm TIL 257; 3:20 pm – 4:40 pm TIL
258. (Livingston Campus)

**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. There will also be a final
project.

** Hw
1** – Due October 2 (in class)

** Hw
2** – Due October 30 (in class)

** Hw-3 **–
Due December 11 (in class)

**Schedule:**

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

§
**Lecture 2
(09/11): **P, NP, Cook-Levin Theorem

§
**Lecture 3
(09/18): **Hierarchy theorems, Ladner’s Theorem

§
**Lecture 4
(09/25): **Oracles and relativization, Space
bounded complexity

§
**Lecture 5
(10/02): **More space bounded complexity

§
**Lecture 6
(10/09): **NL, co-NL, polynomial hierarchy

§
**Lecture 7
(10/16): **Polynomial Hierarchy and alternating Turing machines

§
**Lecture 8
(10/23): **Randomized computation

§
**Lecture 9
(10/30): **More randomized computatios

§
**Lecture
10 (11/6): **Interactive proofs, AM, MA

§
**Lecture
11 (11/13): **Goldwasser-Sipser set lower bound
protocol

§
**Lecture
12 (11/20): **IP = PSPACE

§
** (11/27): **NO CLASS.
(Wednesday is Friday schedule, THANKSGIVING BREAK)

§
**Lecture 13
(12/04): **PCP Theorem

§
**Lecture 14
(12/11): **PCP Theorem II

**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