Organizer(s):

Andrea Lincoln, Boston University

Thatchaphol Saranurak, University of Michigan

Zihan Tan, University of Minnesota

Yinzhan Xu, University of California, San Diego

Description

Even after half a century of intensive research, the computational complexity of many fundamental graph problems remains unsettled. One of the main reasons is that our current frameworks for proving hardness (i.e. conditional lower bounds) do not yet work on these core problems. This workshop aims to bring researchers working on fine-grained complexity of graph problems together with researchers who work at the intersection of related areas and fine-grained complexity to help reduce the current gap in our understanding of fundamental graph problems.

There are many central graph problems in different settings whose complexity is far from settled, and we believe that each can benefit from investigation using the fine-grained-complexity lens. These range from specific classical examples such as whether there exists an algorithm for finding directed global minimum cuts faster than computing √n many max flows to broader areas of inquiry like hardness of approximation for flow-cut problems. To date, most fine-grained hardness of approximation results are for distance problems in graphs. There are no non-trivial fine grained hardness of approximation results for flow-cut problems. While there are strong conditional lower bounds for exactly computing all-pairs minimum cuts in vertex-capacitated graphs, there is no fast approximation algorithm bypassing these lower bounds. This raises the question of whether these lower bounds can be lifted to show approximate hardness. The same status holds for dynamic algorithms for computing matching and flow where we know exact conditional lower bounds but not approximation ones. Showing hardness of approximation for these problems is a major open problem in dynamic algorithms. There have been successes in showing the hardness of approximation of approximation algorithms and fpt-approximation algorithms with polynomial running time. Can we transfer these techniques to the regime of almost-linear running time and the dynamic setting? The workshop will lay the groundwork to address such questions through a series of long-format or tutorial presentations.

Speakers confirmed to date:

• Amir Abboud, Weizmann Institute
• Shyan Akmal, Max Planck Institute for Informatics
• Sepehr Assadi, University of Waterloo
• Soheil Benhezhad, Northeastern University
• Greg Bodwin, University of Michigan
• Karl Bringmann, ETH Zurich
• Nick Fischer, Max Planck Institute for Informatics
• Russel Impagliazzo, University of California, San Diego
• Ce Jin, University of California, Berkeley
• Jason Li, Carnegie Mellon University
• Barna Saha, University of California, San Diego
• Saket Saurabh, Institute of Mathematical Sciences
• Nicole Wein, University of Michigan
• Tianyi Zhang, Nanjing University

FGC Fest: This workshop is the third of three workshops on fine-grained complexity (FGC) that will be held back-to-back at Rutgers in July 2026. Each workshop is self-contained but shares the focus on FGC. FGC Fest is made up of:

• Workshop of Algebraic Techniques in Fine-Grained Complexity, July 20-22, 2026.
• Workshop on Fine-Grained Complexity for String Problems, July 23-25, 2026.
• Workshop on Fine-Grained Complexity for Graph Problems, July 27-31, 2026. (This workshop.)

Call For Participation

Presentations at this workshop are by invitation but others are welcome to attend. There is no fee to attend but registration is required. Please register using the link at the bottom of the page.

Request support: There are limited funds available to provide lodging to students and/or postdocs attending the workshop. In most cases, lodging will be shared with another student/postdoc attending the workshop. Priority will be given to those whose interests best align with the topic and whose attendance is contingent on support, especially students. 

To request support please complete and submit this form by April 15, 2026 for full consideration.

What information is requested in the form? Here are some things we will ask for:

• A short statement (one paragraph) about your research area and your interest in the workshop .
• CV in PDF format (optional).
• Contact information for one faculty member who could speak to how attendance will benefit you. (We will only contact this person if we need more information.)
• Whether you plan to attend another workshop in FGC Fest.

FGC Fest is sponsored by:

Presented in association with the Special Focus on Fine-grained Complexity.