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: sometime on Monday October 24th, email me a PDF file.


Final Project


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

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

Due: Friday December 2nd, 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.

·       Using SAT to solve mathematical problems

o   Lamb. Two-hundred-terabyte maths proof is largest ever.

o   Heule, Kullmann, Marek. Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer.

·       Theory of MapReduce

o   Karloff, Suri, Vassilvitskii. A model of computation for MapReduce.

o   Fish, Kun, Lelkes, Reyzin, Turan. On the Computational Complexity of MapReduce.

·       Unusual Turing-complete models

o   Conway’s FRACTRAN and Game of Life.

o   Conway, Guy. “The Book of Numbers”.

o   Turing machine implemented in Game of Life.

·       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:

o   2005-2014:

·       The Recursion Theorem

o   The 1# language and the Text Register Machine

·       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

·       Zero-knowledge proofs

·       Average case complexity

·       History/Survey on Computational Complexity

o   Fortnow, Homer A Short History of Computational Complexity

o   Goldreich, Wigderson Complexity Theory: A Survey

·       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

·       History of the PCP theorem

o   O’Donnell A History of the PCP Theorem

o   Kolata New Short Cut Found For Long Math Proofs

·       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

·       Further topics in complexity

o   Read a chapter in the Arora-Barak text

·       Misc.

o   Aaronson NP-complete problems and physical reality