CS 598 TMC, Fall 2020

Presentation and Project Guidelines

Presentation

Date: Dec 4 or 9 (during the last 2 classes)

Present one paper (15-20 minutes if working alone, or 20-25 minutes if working in a group of 2, or 25-30 minutes if in a group of 3 -- every member of the group should participate). The format is similar to a conference talk. Spend sufficient time on the introduction (problem statement, background and survey of previous or related results, statement of the new results). Then describe the main ideas behind the new algorithm(s)/hardness proof(s) in the paper. You may not have time to cover all results in the paper, or go into all the technical proof details; pick the part(s) you find most interesting. Point out connection (if any) with techniques we have seen from class. Close with open questions (from the paper, or ones you think of yourself).

Project

Deadline: before Dec 18 Friday 5pm

Write a report (about 10 pages (single-column, single-spaced) if working alone, or about 15 pages if working in a group of 2, or about 20 pages if in a group of 3), comparing 2 or more papers on a common topic in fine-grained algorithms and complexity. One of the papers may be the paper you used for your presentation.

Begin with an introduction of the problem and a general survey. Then describe the new algorithms/hardness proofs in your selected papers. You do not need to explain all the technical details (especially if they are complicated). Present your own (hopefully easier-to-understand) interpretation, in your own words (do not copy or just paraphrase the descriptions from the papers). Point out similarities and differences between the papers, and their strengths and weaknesses. Point out connections (if any) with techniques from class. Close with open questions, as well as your thoughts on future work and any ideas you may have regarding possible further improvements.

Alternative option: do original research! If you succeed in solving an open problem, you can describe your new results in your report (and presentation). In any case, still include a general introduction/survey. If you are not successful, you may still explain your failed attempts, partial results on special cases, new variations of the problem, etc. in your report.

Topics/Papers

Fine-grained algorithms and complexity is a very active area of research, and there are numerous papers to choose from! I have included a random list of papers below as examples, but you are free to find a topic/papers on your own. Fine-grained-related papers can often be found in recent proceedings of the major theory and algorithms conferences such as SODA, FOCS, STOC, ICALP, ITCS, ESA, SOSA, etc., or on the arXiv. Or look for papers from some of the key authors' home pages or DBLP pages. Or look into papers mentioned (but not covered in-depth) in class. Feel free to ask me for advice (besides my scheduled office hours, we can meet on zoom at other times -- just email me to set up an appointment).

Let me know what you choose by mid-November, to verify that your choice is within scope for this course, and does not overlap substantially with other students' choices (or my own lectures).

General tips:

Examples: