Computing Theory Course

Computing Theory

Time: 2:10--5:00 Wednesday and Thursday



If IP=PSPACE, then TCP=NP.
---Class of 2000, M.S. (overheard)

A professor always included this question on his final exams:
"What did you think of this course?"
He discontinued the practice after receiving this response:
"This was the most complete course I ever took.
Anything we didn't go over during class
was covered in the final exam."
---Adapted from Reader's Digest

Two hunters are being pursued by a bear;
one stops to change into his running shoes.
The other tells him he is crazy: there is no
way he can run faster than a bear.
``I don't have to run faster than a bear,''
replies the first. ``I only have to run faster than you.''
The Economist, 18 March 2002

To the students,

This course emphasizes computational complexity and its applications. We will go over, in my opinion, the most interesting and/or important results in the field. You are expected to read the textbook for any background knowledge not covered in the lectures if your undergraduate education has not prepared you for this course. The textbook will, in general, be followed.

The mathematical techniques used in this course are wide-ranging but accessible. Undergraduate discrete mathematics course should be more than adequate. Math majors should be prepared to find standard mathematics used in unexpected ways. Combinatorics, probability, graph theory, number theory, and, to a less extent, group theory are the principal analytical tools. We shall skip predicate logic (Frege 1879) and the associated profound results of completeness and incompleteness (Godel 1930, 1931).

I hope you will be rewarded with the insights, sense of beauty, and applications that some of the results convey. There is also the satisfaction that, unlike many other fields in computer science (including those taught by me), many of the topics will still be taught to students decades from now.

Notes [ 2001, 2002, 2003, 2004, 2005, 2006 ]

  1. 2006.09.20 & 2006.09.21
  2. 2006.09.27 & 2006.09.28
  3. 2006.10.04 & 2006.10.05
  4. 2006.10.11 & 2006.10.12
  5. 2006.10.18 & 2006.10.19
  6. 2006.10.25 & 2006.10.26
  7. 2006.11.01 & 2006.11.02
  8. 2006.11.08 & 2006.11.09
  9. 2006.11.15 (university holiday) & 2006.11.16
  10. 2006.11.22 & 2006.11.23 (mid-term exams)
  11. 2006.11.29 & 2006.11.30
  12. 2006.12.06 & 2006.12.07
  13. 2006.12.13 & 2006.12.14
  14. 2006.12.20 & 2006.12.21
  15. 2006.12.27 & 2006.12.28
  16. 2007.01.03 & 2007.01.04
  17. 2007.01.10 & 2007.01.11
  18. 2007.01.17 & 2007.01.18 (final exams)

Examinations and grading

  1. There was a mid-term exam on November 22, 2006 (closed book).
    • The examination will cover the lecture notes up to p. 335 given on November 1, 2006 (roughly Chapters 1 through 9 of the textbook, excluding Chapters 5 and 6).
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
  2. There was a mid-term exam on November 23, 2006 (closed book).
    • The examination will cover the lecture notes up to p. 335 given on November 2, 2006 (roughly Chapters 1 through xxx of the textbook, excluding Chapters 5 and 6).
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
  3. There will be a final exam on January 17, 2005 (closed book).
    • Location: room 103 of the CSIE building.
    • The examination will cover the lecture notes starting from p. 336 (November 8, 2006).
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
  4. There will be a final exam on January 18, 2005 (closed book).
    • Location: rooms 103 and 104 of the CSIE building (but meet in room 103 first).
    • The examination will cover the lecture notes starting from p. 336 (November 8, 2006).
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
  5. Your grades will be based on the grades of the exams.

The major results covered in the course, time permitting, are listed below for your reference.