CS 666, Fall 2022

Project Guidelines

Abstract-project (5%):

Longer version:

1. Pick a paper that is relevant to course content and relatively recent (publication year 2010 or later).
2. List the full citation of the paper as well as a DOI. (Hint: dblp.org gives you complete information, and also BiBTeX entries.)
3. Write a short summary of the paper (2-3 sentences). Do not copy the abstract verbatim.
4. Say how the paper relates to course content (2-3 sentences).
5. Read pp. 1-4 of the writing-guide by Knuth, Larrabee and Roberts https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf, i.e., points 1-23.
   (You are strongly encouraged to read more than this!)
6. Find three of these points that are violated in the paper that you summarized.
7. For each of these three points, state what the original paper said, why this is a violation to which point, and how you would rewrite the sentence(s) to fix it.

Some comments:

• If LaTeX poses a significant hurdle: learn it! (You will definitely need it during grad studies.) However, I will accept an ASCII-file instead, but note that doing (7) is really difficult in anything but LaTeX.
• Your answers to (2-4) may get posted below for possible use for presentation-projects.
• If the paper is absolutely perfect and violates no points, say so. This will not lead to deduction if indeed there are no violations. (But this is exceedingly rare, so check carefully.)
• If you can't find violations to the points, but there are other places of bad writing in the paper, list those instead. (However, they should be three different ways of being bad.)
• Note that you do not need to understand any details of your chosen paper, you only need to understand roughly what it is about. (Typically you can stop reading after the introduction and maybe a few definitions.)
• Each student should pick their own paper.

Presentation-project (15%):

Long version:

1. Pick a paper that is relevant to course content and relatively recent (publication year 2010 or later). Possible papers from the abstract-project will be posted below (and perhaps some others as well). You are permitted (in fact, encouraged) to pick a paper relevant to your own research interests.
2. Read the paper superficially. Select material from the paper (and/or related papers) that would fill approximately half a lecture of cs466.
3. Read in-depth the selected parts of the paper(s) and understand every step of it. (If some parts are truly incomprehensible, seek help early!)
4. Create slides to present the selected parts of the paper(s). These should ideally include the entire proof, but if that's too long, they should focus on the hardest of the cases. The slides should be identical to the ones used during the presentation.
5. Give a half-lecture presentation about the paper. This can either be done by video or in-person (by appointment, likely on Dec 6). Expected length is 30-45 minutes.
6. Answer questions that I have about the paper and your presentation. This will be done during the presentation (if done in-person), and with a separate appointment (likely on Dec 7) if creating a video.

Some comments:

• Your audience is `typical CS466/666 students'. Do not review material we have seen in class. Do not expect background that we have not seen in class.
• Your main objective is to make the topic easily accessible to the audience. This is worth a significant part of your marks! You should probably ask friends with similar backgrounds to watch your video/presentation and to provide feedback on what was difficult. (Exchanging videos with fellow CS666 students for this purpose is acceptable.)
• Make your video/presentation engaging. (You have probably seen enough bad videos / online-presentations during Covid-shutdowns. Think about what was bad about them, and why they put you to sleep, and avoid those errors!)
• Each student should choose their own paper. Papers on the web site will be marked clearly when they have been taken.

Possible presentation-topics:

• Explore recent improvements to approximation algorithms for special cases of TSP. See for example some recent papers by Sylvia Boyd.
• Explore the (very recent!) improvements to the approximation algorithms for metric TSP by Karlin et al. https://doi.org/10.1145/3406325.3451009
• Some APX-hardness results for geometric problems, and some special cases where they're not APX-hard: https://doi.org/10.1016/j.comgeo.2012.04.001

On finding research papers