Index number for registration: 54420

Phone: (732) 445-3629

FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442

Click here for current
Office Hours.

Teaching Assistant: Sambuddha Roy

Phone: (732) 445-4467

Email: samroy at paul.rutgers.edu

Office: Hill 418

Office Hours: Wednesdays 5:00-7:00

Click here for information about homework.

This year, the texts for the course will be

- Lecture Notes on Complexity Theory by Luca Trevisan.
- Introduction to Circuit Complexity : A Uniform Approach (Texts in Theoretical Computer Science) by Heribert Vollmer

- The Complexity Theory Companion, by Lane A. Hemaspaandra and Mitsunori Ogihara.
- Theory of Computational Complexity, by Ding-Zhu Du and Ker-I Ko (2000).
- Introduction to the theory of complexity, by Daniel Pierre Bovet and Pierluigi Crescenzi (1994).
- Computational complexity, by Christos H. Papadimitriou (1994).
- Finite automata, formal logic, and circuit complexity, by Howard Straubing (1994).
- The graph isomorphism problem : its structural complexity, by Johannes Köbler, Uwe Schöning, and Jacobo Torán (1993).
- Structural complexity, by José Luis Balcázar, Josep Díaz, and Joaquim Gabarró (1988).

The actual list of topics may vary slightly from the list that follows below, depending on the interests of the class.

- The canonical complexity classes, and why they are the fundamental objects of complexity theory. Reducibility, Completeness, and Diagonalization.
- Circuits and Machines (Deterministic, Nondeterministic, and Alternating)
- Material from Chapters 1-2 of [Vollmer]
- Separations (Deterministic and Nondeterministic Hierarchy Theorems)
- Padding and Translational arguments

- Circuit Lower Bounds (Chapter 3 of [Vollmer])
- Subclasses of P (Chapter 4 of [Vollmer])
- Probabilistic Computation, Circuits, and the Polynomial Hierarchy
(Chapter 6 of [Vollmer])
- Undirected connectivity (Randomized and Deterministic Algorithms)
- Primality testing (Randomized and Deterministic Algorithms)
- Arithmetic Circuit Identity Testing

- The Power of Counting
- [Valiant and Vazirani] (unique solutions for SAT)
- Toda's Theorem
- NL/poly = UL/poly

- Derandomization and Pseudorandom Generators: Towards BPP=P
- Interactive Proofs

**Expected Work:** Homework assignments