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: sometime on Monday
October 24th, email me a PDF file.
Final Project
Requirements:
· Roughly 10 pages in
length (reasonable margins, fonts, etc.)
· Must be typeset in Latex (not
Microsoft Word, etc.)
Due: Friday December 2nd,
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.
· Using SAT to solve
mathematical problems
o
Lamb.
Two-hundred-terabyte
maths proof is largest ever.
o
Heule,
Kullmann, Marek. Solving and
Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer.
· Theory of MapReduce
o
Karloff,
Suri, Vassilvitskii. A
model of computation for MapReduce.
o
Fish,
Kun, Lelkes, Reyzin, Turan. On
the Computational Complexity of MapReduce.
· Unusual
Turing-complete models
o
Conway’s
FRACTRAN and Game of Life.
o
Conway,
Guy. “The
Book of Numbers”.
o
Turing machine implemented in Game
of Life.
· 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
o
2005-2014:
http://blog.computationalcomplexity.org/2014/12/favorite-theorems-recap.html
· The Recursion Theorem
o
The 1# language and the Text Register
Machine
· 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
· History/Survey on Computational
Complexity
o
Fortnow,
Homer A
Short History of Computational Complexity
o
Goldreich,
Wigderson Complexity
Theory: A Survey
· 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 of the PCP
theorem
o
O’Donnell
A
History of the PCP Theorem
o
Kolata
New
Short Cut Found For Long Math Proofs
· 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
· Further topics in
complexity
o
Read
a chapter in the Arora-Barak
text
· Misc.
o
Aaronson
NP-complete problems and
physical reality