| Syllabus: |
detailed syllabus in pdf less detailed syllabus in html |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: CSA 1.120A |
| Useful Pointers: |
Theory of Computing Blog Aggregator
P vs. NP poll List of many NP-complete problems Certificate definition of NL is Definition 4.17 (Chapter 4) in Arora & Barak's graduate-level textbook Computational Complexity: A Modern Approach. Complexity of various games and puzzles Manuel Blum's lecture notes (pages 3 and 4) contain a counting argument showing the existence of functions with exponential circuit complexity. Note that he allows arbitrary gates on 2 inputs, whereas we allow only AND, OR, and NOT. |
| Homework: | Posted on Blackboard. |
| Exams: | The three exams will be held in class on the following dates: Exam 1 on Thursday, February 17; Exam 2 on Thursday, March 24; and Exam 3 on Thursday, May 5. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). |