G22.3350-001 Honors Theory of Computation
Honors Theory of Computation (G22.3350), Spring 2001
Table of Contents:
Administrative Stuff (who?where?when?)
Brief Course Description
Handouts
Prerequisites
Grading
Textbooks
Brief Lecture Summaries
FAQs, links, random stuff, etc.
Administrative Stuff
Lecturer: Prof. Yevgeniy Dodis .
Office: WWH-508, tel: 212-998-3084,
e-mail: dodis@cs.nyu.edu .
Lectures: M,W 3:30-4:45pm, WWH-513.
Office hours: W 5-6pm.
Final Exam: May 2, 2pm, WWH-513, closed book, one 8.5x11 sheet of
notes allowed.
Brief Course Description
This is an advanced graduate course on the fundamentals of theory of
automata, 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
regular languages, grammars, Turing machines, logic, 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.), and, if time
permits, some advanced topics, like foundations of cryptography,
probabilistically checkable proofs, approximation algorithms, parallel
computation, etc. The emphasis will be put on the understanding of the
material and the proof techniques used.
Handouts
Prerequisites
General ease with algorithmic concepts, elementary logic and
good understanding of discrete probability are highly recommended.
Grading
Approximately one problem set will be given every two weeks. Problem
sets are extremely important for your understanding of the material,
and will amount to approximately 40% of the grade. The rest will be
given to the exams. Tentatively we will have both the midterm and the
final exam. In some cases, the grade could also be partially based on
class participation, so speak up if you have something interesting to
say or ask!
For writing and problem set policies, refer here . Briefly, you are allowed (but not
encouraged) to collaborate with other students in the class on
your homework, as long as you: 1) understand the solution; 2) write it
up neatly and by yourself ; 3) be honest and acknowledge the
people you worked with; 4) do not consult outsiders, course bibles,
etc. Remember, this is an honors class, there is no much point in
cheating.

Textbooks
Michael Sipser. Introduction to the
Theory of Computation . PWS Publishing, 1997.
Christos Papadimitriou. Computational Complexity . Addison Wesley,
1994.
FAQ's, links, random stuff, etc.
Back to the top