198:509: Foundations of Computer Science

Meeting times and locations: Mondays and Wednesdays, 1:40--3:00 Hill 120.
Index number for registration: 12220

Professor Eric Allender

Phone: (732) 445-2001 ext. 3629
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.

Phone: (732) 445-2001 Ext 9734

Email: (See Yang's home page .)
Office: To be announced.
Office hours for TA: To be announced

The text for the class is: Theory of Computation by Dexter Kozen. It appears that the book is also available in electronic form. Here is information about errata in the textbook. Let me know about additional errors as you discover them. We will also augment with some material on Kolmogorov complexity, by Lance Fortnow.

Rough Outline

Complexity
- Basic Notions (Chapters 1-3)
- Small Space Classes, Reducibility, and Completeness (Chapters 4-6)
- Alternation, PSPACE, and the Polynomial Hierarchy (Chapters 7-10)
Logic
- Basics (Chapter E)
- Complexity of Logical Theories (Chapters 21-24, and B)
- Second-Order Logic (Chapters 25-27) [Did not cover]
- Undecidability, Incompleteness
Computability
- Basics, Recursion Theorem (Chapters 33-34)
- The Arithmetic Hierarchy (Chapters 35-36)
- Incomplete Degrees (Chapters 37-38)
- Kolmogorov Complexity
Possible Other Topics
- Probabilistic Computation (Chapters 13 and 14) (Selected by the class)
- #P and Toda's Theorm (Chapters F and G) (Selected by the class)
- Berlekamp's Factorization Algorithm (Chapters B & D)
- The Gap and Speed-Up Theorems (Chapter 32)
- Abstract Complexity (Chapter J)
- The Analytic Hierarchy and Applications (Chapters 39-41)
- Various Topics in Complexity (Various Chapters)

Prerequisites:Graduate standing.

Expected Work: There will be one midterm and one (take-home) final. The FINAL is now available. The midterm will be held in class. In addition, there will be homework every two or three lectures; this homework is a major consideration in assigning grades.