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