Course Project

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 26th, in class.


Final Project

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

o   Feferman The nature and significance of Godel’s incompleteness theorems

·         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

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

·         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. / Philosophy

o   Aaronson NP-complete problems and physical reality