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 26th, in class.
This should be roughly ten pages in length.
Due: Friday November 30th, in class.
Some suggested topics
· Parsing: LR(k) parsers, etc.
· Discussion of Godel's incompleteness theorem & Russell's paradox
· 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
· 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
· Misc. / Philosophy
o Aaronson NP-complete problems and physical reality