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.
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.
· 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 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, Guy. “The Book of Numbers”.
· Fortnow’s Favorite Theorems (many of which are covered in the Arora-Barak text)
· The Recursion Theorem
· Complexity of Equilibria
o Daskalakis, Goldberg, Papadimitriou The complexity of computing a Nash equilibrium
· 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 Gasarch The P=?NP Poll
o Cook P vs NP
· History of the PCP theorem
o O’Donnell A History of the PCP Theorem
· Hilbert's 10th problem
· Kolmogorov Complexity
o Chaitin's constant, etc.
· Further topics in complexity
o Read a chapter in the Arora-Barak text
o Aaronson NP-complete problems and physical reality