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

Lecturer: Prof. Yevgeniy Dodis, dodis(at)cs.nyu.edu, (212) 998-3084, room 508, WWH. Office hour: Thursday 5-6
Meeting Time/Place: TR 3:30-4:45, room 102, WWH.
Mailing list: To subscribe to the class list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/g22_3350_001_sp03
To post a message to all the list members, send email to g22_3350_001_sp03@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

This is going to be a somewhat easier version of my Spring 01 course.

However, several important changes will take place. I will no longer cover finite automata theory and cover much less logic. Their place will be taken by more modern topics such as derandomization, interactive protocols, hardness of approximation, cryptography and parallel algorithms. Since this is no longer a required class, the homework load will be much lighter (approximately one short homework every 2-3 weeks), and, more generally, the emphasis will be on the understanding of state-of-the-art material rather than on doing exercises. The course will have no midterm, but will have a final exam.

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.