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:
http://blog.computationalcomplexity.org/2005/12/favorite-theorems-first-decade-recap.html
o
1975-1984:
http://blog.computationalcomplexity.org/2006/12/favorite-theorems-second-decade-recap.html
o
1985-1994:
http://eccc.hpi-web.de/eccc-reports/1994/TR94-021/index.html
o
1995-2004:
http://blog.computationalcomplexity.org/2004/12/favorite-theorems-recap.html
·
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