G22.3350-001 Honors Theory of Computation

# Honors Theory of Computation (G22.3350), Spring 2001

Brief Course Description
Handouts
Prerequisites
Textbooks
Brief Lecture Summaries

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.

## Prerequisites

General ease with algorithmic concepts, elementary logic and good understanding of discrete probability are highly recommended.

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.