198:509: Foundations of Computer Science (for Fall, 2017)

Meeting times and location: Mondays and Wednesdays in Beck Hall 252 (Livingston); 3:20--4:40

Professor Eric Allender

Phone: (848) 445-7296
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.

Grader: Harsha Srimath Tirumala

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.
Click here to find out about what was covered in class, and what material you should read next.

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) [If there is time.]
- 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)
- #P and Toda's Theorm (Chapters F and G)
- 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)
- Gödel's Completeness Theorem: Every valid statement has a proof (Notes)

Prerequisites:Graduate standing.

Expected Work: There will be one midterm and one (take-home) final. 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.