CmpE58G: Advanced Topics in
Theoretical Computer Science
Spring Semester 2008
Announcements
· Our next reading can be found at http://www.hutter1.net/ai/pfastprg.htm.
· Place from now on: The seminar room (#16).
· First meeting: February 20, ETA A6, 13:00. (We’ll change rooms quickly, so be there on time.)
· New announcements will be added to the top as they arrive. Please follow this announcements page frequently.
Subject:
This course assumes familiarity with (or a willingness to learn really quickly
about) basic automata-, computability-, and complexity-theoretic notions, and
builds on them to provide a wider coverage of the theoretical computer science
field.
Textbook:
Computational Complexity: A Modern Approach, S. Arora and B. Barak, www.cs.princeton.edu/theory
Instructor:
Cem Say
References:
Introduction to the Theory of Computation (2nd edition), M. Sipser, Course
Technology, 2005.
and
Gems of Theoretical Computer Science, U. Schöning and R. Pruim, Springer, 1998
and
Oded Goldreich’s
lecture notes
Topics (may change suddenly, if we see a new and good paper to read):
1. Diagonalization and relativization
2. Ladner's theorem
3. the priority method
4. circuit
complexity
5. the
parity function
6. neuroidal computation
7.
acceleration
8. probabilistic
algorithms
9. interactive proofs and zero knowledge
10. streaming computation
Prerequisite:
Some
prior knowledge of the theory of computation (Talk to the instructor if you
have problems in this regard.)
Computer Usage:
None
Laboratory projects:
None.
Mathematics:
A lot of
proofs and hard work.