Fine-grained complexity is currently one of the most rapidly developing areas of algorithmics. Research in this field regularly appears at top-tier conferences such as STOC, FOCS, SODA, and ICALP, and dedicated courses are taught at leading universities in both Europe (e.g., ETH Zurich, Saarbrücken) and the United States (e.g., MIT, Stanford, Harvard). The goal of this seminar is to present some of the recent and most interesting results in this field.
The central aim of fine-grained complexity is to classify problems solvable in polynomial time. For example, in the All-Pairs Shortest Paths (APSP) problem, we seek distances between every pair of vertices in a weighted directed graph. While a cubic-time O(n^3) solution is easy to obtain, and perhaps surprisingly, no significantly faster algorithm is known. At the same time, we are unable to prove that such an improvement is impossible. This motivates the study of entire classes of problems that are equivalent to APSP (in an appropriate sense): an O(n^(3−ε)) -time algorithm for any one of them would yield substantially faster algorithms for all others.
While prior experience with the fine-grained complexity course may be helpful, it is not required. The seminar will focus on techniques that are accessible to students who have completed the course in Discrete Mathematics or Algorithms and Data Structures.
Every participant will need to present some results or techniques from the field, either based on conference papers or slides / materials from other universities.
