#

##
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

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.

** Homework 1: (due Feb. 13)**.
(.pdf, .tex template,
.ps sample)
** Homework 2: (due Mar. 4)**.
(.pdf, .tex template,
.ps sample)
** Homework 3: (due Mar. 25)**.
(.pdf, .tex template,
.ps sample)
** Homework 4: (due Apr. 10)**.
(.pdf, .tex template,
.ps sample)
** Homework 5: (due Apr. 29)**.
(.pdf, .tex template,
.ps sample)

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.