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).

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.

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:**

- Browse through papers by conferences or by authors on DBLP
- Search for papers with Google Scholar
- UIUC library's proxy bookmarklet should give you access to conference and journal articles
- Note: some papers have multiple versions, in conferences, in journals, and/or on the arXiv; the journal version (if available) is usually the most up-to-date

**Examples:**

- All-pairs LCA in DAGs: Breaking through the O(n^{2.5}) barrier by Grandoni, Italiano, Lukasiewicz, Parotsidis, and Uznanski (SODA'21)
- Monochromatic triangles, triangle listing and APSP by Vassilevska W. and Xu (FOCS'20)
- Scheduling lower bounds via AND subset sum by Abboud, Bringmann, Hermelin and Shabtay (ICALP'20)
- Towards optimal set-disjointness and set-intersection data structures by Kopelowitz and Vassilevska W. (ICALP'20)
- Output-sensitive subset sum by Bringmann and Nakos (STOC'20)
- New hardness results for planar graph problems in P and an algorithm for sparsest cut by Abboud, Cohen-Addad, and Klein (STOC'20)
- Data structures meet cryptography: 3SUM with preprocessing by Golovnev, Guo, Horel, Park, and Vaikuntanathan (STOC'20); and The strong 3SUM-indexing conjecture is false by Kopelowitz and Porat ('19)
- Monochromatic triangles, intermediate matrix products, and convolutions by Lincoln, Polak, and Vassilevska W. (ITCS'20)
- Equivalences between triangle and range query problems by Duraj, Kleiner, Polak, and Vassilevska W. (SODA'20)
- Algorithms and lower bounds for cycles and walks: small space and sparse graphs by Lincoln and Vyas (ITCS'20)
- SETH says: Weak Frechet distance is faster, but only if it is continuous and in one dimension by Buchin, Ophelders, and Speckmann (SODA'19)
- Towards tight approximation bounds for graph diameter and eccentricities by Backurs, Roditty, Segal, Vassilevska W., and Wein (STOC'18)
- More consequences of falsifying SETH and the orthogonal vectors conjecture by Abboud, Bringmann, Dell, and Nederlof (STOC'18)
- Tree edit distance cannot be computed in strongly subcubic time (unless APSP can) by Bringmann, Gawrychowski, Mozes, and Weimann (SODA'18)
- Matching triangles and basing hardness on an extremely popular conjecture by Abboud, Vassilevska W., and Yu'18
- Distributed PCP theorems for hardness of approximation in P by Abboud, Rubinstein, and Williams (FOCS'17) (there is also a survey on SETH vs. approximation by Rubinstein and Vassilevska W.'19)
- Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product by Bringmann, Grandoni, Saha, and Vassilevska W. (FOCS'16)
- Tight hardness results for maximum weight rectangles by Backurs, Dikkala, and Tzamos (ICALP'16)
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made by Abboud, Hansen, Vassilevska W., and Williams (STOC'16)
- Unifying and strengthening hardness for dynamic problems via the OMv conjecture by Henzinger, Krinninger, Nanongkai, Saranurak (STOC'15)
- Popular conjectures imply strong lower bounds for dynamic problems by Abboud and Vassilevska W. (FOCS'14)