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: Friday October 25th, in-class.
· 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
· Kolmogorov Complexity
o Chaitin's constant, etc.
· History of P vs NP
o Gasarch The P=?NP Poll
o Cook P vs NP
· The Recursion Theorem
· 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
· 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)
· Complexity of Equilibria
o Daskalakis, Goldberg, Papadimitriou The complexity of computing a Nash equilibrium
o Aaronson NP-complete problems and physical reality