#

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

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.
** Homework 1: (due Feb. 10)**.
(.pdf, .tex template,
.ps sample)
** Homework 2: (due Feb. 26)**.
(.pdf, .tex template,
.ps sample)
** Homework 3: (due Mar. 23)**.
(.pdf, .tex template,
.ps sample)
** Homework 4: (due Apr. 8)**.
(.pdf, .tex template,
.ps sample)
** Homework 5: (due Apr. 27)**.
(.pdf, .tex template,
.ps sample)

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