198:538: Complexity of Computation

Meeting times and locations: Mondays and Wednesdays, 2:50--4:10, in Hill 120
Index number for registration: 54420

Professor Eric Allender

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

We will augment with notes and papers, as needed. In addition, students may find some of the following books to be useful as references. However I do not anticipate making specific reference to these materials.

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).

Rough Outline

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

Prerequisites: 198:452, 198:509, and 198:513, OR familiarity with the basic notions of data structures and algorithms, and common models of computation (e.g., Turing machines, finite automata, etc.)

Expected Work: Homework assignments

NOTES for the 1998 offering of the class are available by clicking here.

Some notes for the 2000 offering of the class are available by clicking here.