CPSC506 Reading Project

The class reading project is an opportunity for you to learn in more depth about a topic in complexity theory of interest to you, or to apply some material that you've learned in this course to a problem in your research area. You could either pick a research paper to study in depth, pick a topic and synthesize key ideas from a few papers on that topic, or read a survey paper.

I've included some suggestions below. Some are classical papers in the field, others quite recent. Don't feel limited by these - if you have a different paper or topic you'd like to study, run it by me before commiting to it. Let me know what paper or topic you will study by Wednesday March 18.

Once you have chosen a paper or topic, please arrange a time before the end of March to discuss with me how it's going: what you are learning from the paper, what's confusing, how you might structure your presentation about the paper. I'll be happy to meet more than once if you'd like.

Presentation:

You'll share what you've learned a class presentation. We will schedule a date in mid-April for the presentations. In your presentation, motivate your choice of topic, give an overview of the main results, and insight to the underlying technigues. Share ideas for future work. Use the board, slides, or both. Use this as a chance to give good presentations! Find simple examples to illustrate the more complicated concepts. Don't try to squeeze in too much material, but rather try to get the important ideas across. If you have a draft of your presentation ready at least 48 hours before the presentation date, I'll be happy to provide feedback.

Grade:

Your grade will be based primarily on your presentation.

Paper and Topic Suggestions

The PCP Theorem by gap amplification, by Irit Dunir. This is a considerably simplified proof of the result that NP = PCP(log n, 1), drawing on lots of beautiful ideas in complexity theory.
The Unique Games Conjecture of Subhash Khot has unified many threads of complexity theory, and if true has lots of implications for hardness of approximation. See also this survey by Lipton and Regan.
Hardness versus Randomness, by Noam Nisan and Avi Wigderson. This is a classic paper on the construction of pseudorandom bit generators, a topic that is central to questions such as whether BPP = P or the (strong) PCP theorem.
Stable leader election in population protocols requires linear time, by David Doty and David Soloveichik. Population protocols are closely related to chemical reaction systems, which we'll study later in the course, and there's a lot of progress on the theory of such systems because of its connections also with distributed computing. This paper proves a lower bound on a central problem in the field, and raises lots of other interesting questions. Can the proofs in this paper be simplified?
Zero Knowledge Interactive Proofs of Knowledge: A Digest, by Martin Tompa. A fun introduction to a topic that ties together interactive proofs, number theory, and cryptography.
Digital Mechanical Metamaterials or other work of Patrick Baudisch. Models of Computation Meets Mechanical Engineering: Ways to perform logic computations mechanically, using 3D printed objects.
The Computational Complexity of Estimating Convergence Time by Nayantara Bhatnagar Andrej Bogdanov and Elchanan Mossel. See also here.
This paper has some nice results on the hardness of approximating convergence times of Markov Chain Monte Carlo algorithms The proofs are not too complicated and connect with interactive proof systems as well as random walks on graphs.