Seminar on Recent Breakthroughs in Fine-Grained Complexity

This seminar is offered for students enrolled in the Mathematics Master as module S4C1 “Graduate Seminar on Discrete Optimization” as well as students enrolled in the Computer Science Master as module MA-INF 1205 with the same title. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

  • Study a scientific paper (see references below)
  • Present the main ideas of the paper in a talk (45 minutes talk + 15 minutes questions)
  • Participate in discussions on the topic of the seminar
  • Submit a written report (in own words)

Schedule

If you want to participate in the seminar, please contact Prof. Dr. Anne Driemel with your topic preference from the literature list. The first preparation meeting will take place on Friday 29. January 2027 in room 2.074 (Informatik V, 2. OG) at 11 am. The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8.

Content

Fine-grained complexity asks how fast computational problems can be solved, seeking to determine the precise running times of algorithms beyond the distinction between polynomial and exponential time. Hypotheses concerning problems such as SAT, 3SUM, all-pairs shortest paths, and hyperclique have guided this research by supporting conditional lower bounds for many other problems.

This graduate seminar explores recent breakthroughs that challenge these hypotheses and open new directions in algorithm design. Through selected foundational and recent papers, participants will study fine-grained reductions, algebraic techniques, and the consequences of faster algorithms for graph problems, computational geometry, and satisfiability. The seminar assumes familiarity with algorithms, complexity theory, and basic linear algebra.

Literature (tentative)

The current state of the art is highly volatile. Some of the newer breakthrough results have been claimed, but have not been verified. This list will be frequently updated as things unfold.

  1. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. JCSS, 2001. https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf
  2. Virginia Vassilevska Williams and Ryan Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. FOCS, 2010. https://www.cs.cmu.edu/~ryanw/tria-mmult.pdf
  3. Allan Grønlund and Seth Pettie. Threesomes, Degenerates, and Love Triangles. FOCS, 2014. https://arxiv.org/abs/1404.0799
  4. Sankeerth Rao Karingula and Shachar Lovett. A Simplified Proof of Polynomial Improvements for 3SUM and APSP. October 2026 preprint. https://eccc.weizmann.ac.il/report/2026/247/
  5. Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu. 3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized. October 2026 preprint. arXiv:2610.42012v1. https://arxiv.org/abs/2610.42012v1
  6. Nick Fischer. The Hyperclique Hypothesis Is False. November 2026 preprint. arXiv:2611.03880. https://arxiv.org/abs/2611.03880
  7. Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu. The 3-Uniform Hyperclique Hypothesis Is False. November 2026 preprint. arXiv:2611.06813. https://arxiv.org/pdf/2611.06813

Page Tools