G22.3350-001 (Honors Theory of Computation), Spring 2004

Lecturer: Prof. Yevgeniy Dodis, dodis(at)cs.nyu.edu, (212) 998-3084, room 508, WWH. Office hour: Thursday 3:15-4:15
Meeting Time/Place: TR 2-3:15, room 613, WWH.
Mailing list: To subscribe to the class list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/g22_3350_001_sp04
To post a message to all the list members, send email to g22_3350_001_sp04@cs.nyu.edu. Please, post only messages interesting to everybody taking the class. Specific class-related questions and most of your other correspondence should be directed to the instructor.

Lecture Summaries (from last year, subject to change)

See the page for the Spring 2003 class for more information.

Brief Course Description:

This is an advanced graduate course on the fundamentals of theory of computability and computation. The objective of the course is to understand questions of the form: "what is computation?", "which computational problems can be solved?", "which problems are easy/hard?", etc. In trying to answer these metaphysical questions, we will introduce many possible models of computation, study the relationship between these models, learn how to formally show that some problems are harder than others, and that some problems are not solvable at all! We will study a wide range of topics, including Turing machines, recursion theory, (un)decidability, diagonalization, oracles, randomization and non-determinism, time and space complexity, reductions, complete problems, games, interactive protocols, various complexity classes (P, NP, coNP, L, RP, ZPP, PSPACE, EXP, IP, etc.), foundations of cryptography, probabilistically checkable proofs, approximation algorithms, parallel computation, imperfect random sources, etc. The emphasis will be put on the understanding of the material and the proof techniques used.

Textbooks:

Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997.
Christos Papadimitriou. Computational Complexity. Addison Wesley, 1994.