CS 860 Final Project

For the final project, you will be asked to do one of the following:

• Work on an open problem in complexity theory
• Survey a topic in complexity theory
• Present a recent work in complexity theory
• Show how complexity theory fits your research area (for graduate students only)

The ideal project would be a problem/topic that you are excited about - this often brings one the most joy. If you need some guidance in picking a problem to present on, I will be happy to meet with you to hone into a problem of your liking.

The topics below are simply a suggestion. If you have another topic of your interest which is not covered here, I will be happy to try and work out with you a possible project on your topic of choice.

Final projects must be done individually.

Timeline for the final project

• October 17th: project proposals due
• December TBD: project presentations

Template for final project

For the final project, we strongly recommend you to write it in LaTeX. A template that you can edit accordingly is given here.

Research-based projects

I highly encourage you all to try your hands at an open problem! It is an amazing and enriching experience, and you may end up solving it by the end of the class!

For those of you (undergrads) who want to use this opportunity to start working on some research problems (perhaps as a pre URA or an URA), here are people that you can check out their webpages/try to reach out to, or resources at your disposal, for you to look for suitable projects:

• Algorithms and Complexity faculty webpage
• Combinatorics and Optimization faculty webpage
• CrySP faculty webpage
• UW URA webpage

A good strategy to find interesting open problems is to look at a particular faculty’s advanced graduate course’s webpage and see the topics they are interested in and the open problems in the area that they would be interested in. You can use your final project to get a deeper understanding in such an area where your interests match.

Possible Topics for Final Project

• Fleming, Kothari, Pitassi Semialgebraic proof systems & algorithms survey
• PCPs and their applications in hardness of approximation, or in the blockchain
• Hardness of approximation and Unique Games Conjecture
• Interactive Proofs
• Fine-grained complexity of algorithms: how (a lot of) hardness for hard problems translates into hardness for easy problems
• Coding Theory in Complexity Theory (locally decodable/correctable codes)
• Complexity in Number Theory: a reference on number theoretic algorithms by Shoup
• Complexity in Algebra and Algebraic Geometry Ideals, Varieties and Algorithms and Using Algebraic Geometry
• Complexity of Cryptography: lecture notes by Pass and Shelat
• Extension Complexity of Polytopes
• Smoothed Analysis of Algorithms
• Semidefinite Programming and Sum of Squares decompositions: Sum of Squares solve everything?
• Semidefinite Extension Complexity (i.e. spectrahedral lifts) of convex sets
• Boaz’s Sum of Squares lecture notes with open questions at the end