Organizer(s):

Josh Alman, Columbia University

Description

Fine-grained complexity theory aims to prove that for many different computational problems, the current best algorithms cannot be substantially improved. For many of the problems of interest, including those at the core of the hardness assumptions used throughout the theory, the best known algorithm is algebraic in nature, using tools like fast matrix multiplication, polynomial approximations, and polynomial identity testing. This is perhaps very surprising, since a priori, these problems appear to have nothing to do with algebra. Some prominent examples include the best known algorithms for Orthogonal Vectors, All-Pairs Shortest Paths, Nearest Neighbor Search, and Subgraph Isomorphism problems like Triangle Detection, k-Clique, and Longest Path.

Recently, algebraic techniques have been used to design surprisingly fast algorithms for problems that were previously believed to be impossible. These algebraic algorithms have explained why researchers have had trouble proving fine-grained lower bounds for these problems. Some recent examples include Correlation Detection, variants on the Traveling Salesperson Problem, Cycle Detection, and small circuit constructions. Algebraic techniques have also been used as components of fine-grained reductions, in order to prove new fine-grained hardness results. For example, polynomial approximations are at the heart of recent techniques for proving fine-grained average-case hardness and yielding fine-grained cryptographic constructions, and hardness for approximate and exact closest pair problems.

Finally, fine-grained hardness has given a new lens to explore classical and fundamental algebraic computational problems like solving systems of polynomial equations and closest vector problems.

This workshop aims to bring together researchers working on or interested in these algebraic techniques. There are many open questions related to their power and limitations to explore, and it is likely that techniques developed for one problem may be used in other areas of fine-grained complexity as well. The workshop will contain a mix of tutorials to get participants up-to-speed, talks on recent results, and time for working together on finding new connections and tackling open problems.

Current list of confirmed speakers:

• Amir Abboud, Weizmann Institute of Science
• Shyan Akmal, Max Planck Institute for Informatics
• Cornelius Brand, Regensburg University
• Jan van den Brand, Georgia Institute of Technology
• Sasha Golovnev, Georgetown University
• Kevin Pratt, Columbia University
• Ryan Williams, Massachusetts Institute of Technology
• Yinzhan Xu, University of California, San Diego

FGC Fest: This workshop is the first 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. (This workshop.)
• Workshop on Fine-Grained Complexity of String Problems, July 23-25, 2026.
• Workshop on Fine-Grained Complexity of Graph Problems, July 27-31, 2026.

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.