CS 535: Complexity Theory, Fall 2020 Term Paper Instructions
Due: 8:00PM, Thursday, December 10, 2020.
The term paper for CS 535 is an opportunity to explore a topic in complexity theory that interests you. The goals are to gain experience
Independently reading and synthesizing research papers,
Presenting research papers to an audience of your peers, and Critically evaluating written technical work.
The final paper you submit will be a review of a research article or survey in complexity theory on a topic we did not cover in detail in class. The review should be targeted to other students in the class—in fact, an important component of the project will be reviewing each others’ work and providing constructive feedback. You can assume they are familiar with the topics we’ve studied (time/space complexity, boolean circuits, randomized computation, interactive proofs, the statement of the PCP theorem, counting complexity), but not with the specific models and definitions in the topic you are investigating.
Some suggestions for potential project topics will be listed on the course website. You are not required to choose from among these topics and are encouraged to select your own, especially if they relate to your research interests.
You should begin with a few paragraphs describing, at a high-level, the contributions of the paper you are reviewing. This introduction should emphasize conceptual contributions and why they are important, avoiding technical definitions and details.
Next, you should describe the main results of the paper at a technical level, giving precise theorem statements. To set this section up, you will need to begin by formally describing whatever models, definitions, and preliminary facts are needed to understand them.
Then you should choose one of these main results and give a detailed proof. Depending on the topic you choose, it may be difficult to do this concisely. If that is the case, you may decide to prove a special case of the result (that illustrates most of the main ideas). You might also “black-box out” technical lemmas that require lengthy calculations but are not so conceptually important, so long as these lemmas are stated precisely and you can prove how they fit together.
Finally, your paper should conclude with further discussion of the implications of the results you’ve described and directions for future research.
To the extent which you are able, think about how your review can provide “added value” to the paper you are reviewing. This may include
Connecting the topic to other topics we’ve studied in class,
Summarizing subsequent literature that follows up on the paper you’ve chosen,
1
Supplying missing details in the proofs,
Generalizing the arguments to prove stronger statements,
Simplifying some of the proofs to highlight the main conceptual points (perhaps at the expense of generality), or
Adding new intuitive interpretations for technical statements and arguments.
This can be challenging but results in a much more rewarding project. Please indicate in your report whenever you are able to make these contributions.
You may work on the project either individually or in pairs. To keep you on track with the project, we have provided several intermediate milestones with deadlines below. The term paper counts for 25% of your grade, which is broken down into the following components.
Topic Selection (Friday 11/6) Submit to Gradescope the topic you are investigating, the paper you are reviewing, and your project partner (if applicable).
Draft Due (Friday 11/20, 3%) Upload a draft of your paper to Gradescope. The PDF should be anonymized for peer feedback. If you are working with a partner, only one of you needs to submit.
Draft Peer Review (Wednesday 11/25, 3%) Following the draft submission deadline, we will randomly assign everyone a peer’s anonymized draft to provide a few paragraphs of respectful and constructive feedback. What did the author(s) do well? What could they improve? Are the proofs convincing? Is enough intuition provided to support the technical statements? Are there any places that are unclear or where special knowledge is assumed? Is there a clear plan for writing any sections that have yet to be written?
Final Paper Due (Thursday 12/10, 16%) Submit the final anonymized PDF of your paper to Gradescope.
Final Peer Review (Friday 12/18, 3%) Provide constructive feedback to a different peer, as before. Congratulations on completing the semester!
2