198:509: Foundations of Computer Science
Meeting times and location: Mondays and Wednesdays in Beck Hall 252 (Livingston); 3:204:40
Phone: (848) 4457296
FAX: (732) 4450537
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
(Topics will be covered in a different order.)
 Complexity
 Basic Notions (Chapters 13)
 Small Space Classes, Reducibility, and Completeness (Chapters 46)
 Alternation, PSPACE, and the Polynomial Hierarchy (Chapters 710)
 Logic
 Basics (Chapter E)
 Complexity of Logical Theories (Chapters 2124, and B)
 SecondOrder Logic (Chapters 2527) [If there is time.]
 Undecidability, Incompleteness
 Computability
 Basics, Recursion Theorem (Chapters 3334)
 The Arithmetic Hierarchy (Chapters 3536)
 Incomplete Degrees (Chapters 3738)
 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 SpeedUp Theorems (Chapter 32)
 Abstract Complexity (Chapter J)
 The Analytic Hierarchy and Applications (Chapters 3941)
 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 (takehome) 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.