542 Theory of Computation
Brief Description. This course will be an introduction to the
theory of computational complexity. Most of the course will be based on
Part Three of the textbook which includes the following topics: time complexity,
NP-completeness, space complexity, the hierarchy theorems, relativization,
circuit complexity, approximation algorithms, probabilistic algorithms,
alternation, interactive proofs systems, parallel computation and cryptography.
Additional topics in computability theory (from Chapter 6 of the textbook)
and in small-depth circuit complexity may be covered.
Instructor. Alexis Maciel
Office: Science Center 379
Office Hours. Monday and Wednesday 11:00--12:00, Tuesday and
Thursday 10:00--11:30, and by appointment.
Michael Sipser, Introduction to the Theory of Computation, PWS
Publishing Company, Boston, MA, 1997.
| Homework assignments
| One test
| Final exam
The assignment policy for the course will be stated on the first assignment.
Tentative date for the test: March 10.