Course Project

Students enrolled in 501 must complete a course project, which is an in-depth study on a topic relevant to the coursework. The intent is not to develop original research ideas, but to learn about some more advanced topics in the theory of computation, or to learn how this field relates to other areas.


Project Proposal

A brief description of the topic that you plan to study and the paper(s) that you plan to read. The length should be between one-half and one page in length.

Due: Friday October 25th, in-class.


Final Project


·         Roughly 10 pages in length (reasonable margins, fonts, etc.)

·         Must be typeset in Latex (not Microsoft Word, etc.)

Due: Friday November 29th, by email.


Some suggested topics

You are free to choose a topic that is not on this list, but please chat with me first about its suitability.

·         Aaronson Is P versus NP formally independent?

·         Hilbert's 10th problem

o   Davis Hilbert's 10th problem is unsolvable

·         Kolmogorov Complexity

o   Chaitin's constant, etc.

o   Li, Vitanyi An Introduction to Kolmogorov Complexity and its Applications

·         History of P vs NP

o   Sipser History and status of the P vs NP question

o   Gasarch The P=?NP Poll

o   Cook P vs NP

·         The Recursion Theorem

o   The 1# language and the Text Register Machine

·         History/Survey on Computational Complexity

o   Fortnow, Homer A Short History of Computational Complexity

o   Goldreich, Wigderson Complexity Theory: A Survey

·         History of the PCP theorem

o   O’Donnell A History of the PCP Theorem

o   Kolata New Short Cut Found For Long Math Proofs

·         Further topics in complexity

o   Read a chapter in the Arora-Barak text

·         Fortnow’s Favorite Theorems (many of which are covered in the Arora-Barak text)

o   1965-1974:

o   1975-1984:

o   1985-1994:

o   1995-2004:

·         Zero-knowledge proofs

·         Average case complexity

·         Complexity of Equilibria

o   Daskalakis, Goldberg, Papadimitriou The complexity of computing a Nash equilibrium

o   Papadimitriou On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

·         Misc.

o   Aaronson NP-complete problems and physical reality