Masterpieces in Theoretical Computer Science (7.5 hp)

Course Format

Each masterpiece is covered as follows:

1. A 2 hour lecture in which a high level view of the masterpiece is presented (e.g. some necessary background, statement of the result, significance/impact/applications, key ideas of the proof, or other material as appropriate)
2. The students do some reading, and are given some questions (a few different sets of questions). Examples of possible types of questions are:
   • Filling in missing gaps in a Lemma.
   • Analyzing whether some generalization is possible and if not what the main obstacle is.
   • Figure out why some assumption used is needed.
   • Compare the result to some similar result.
   • Work out the details of some application of the result.
   • Surveying further work on the topic.
3. A 2 hour discussion meeting, where we discuss the topic together, dig into parts that are not clear, go over the homework questions, etc
4. For each discussion meeting, each student writes a (brief) report discussing the questions they were assigned.

In addition to the masterpieces covered in class, each student will give a 45 minute presentation of some classic result. (A list of suggestions will be available.)