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.
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 25th,
in-class.
Final Project
Requirements:
·
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
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
·
The
Recursion Theorem
o
The 1# language and the Text Register
Machine
·
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.
o
Aaronson
NP-complete problems and
physical reality