A traditional goal of complexity theory is to distinguish between problems that are computationally tractable and those that are not. The tractable, so-called "easy", problems are solvable in polynomial time and form the complexity class P. From a practical standpoint, however, even problems solvable in cubic or quadratic time may be impossible when the input data is large enough. As technology advanced and problem sizes grew, a more nuanced understanding of the complexity of problems in P became necessary, giving rise to the relatively new field of fine-grained complexity.
Fine-grained complexity seeks to explore the complexity of algorithms beyond the traditional coarse distinction between polynomial-time and NP-hard problems. The central idea is to investigate the relationships between different computational problems and identify those that are "hard" in a more fine-grained sense. This is accomplished through the use of fine-grained reductions, which not only preserve the worst-case running time but also the dependence on various parameters, such as input size, dimensionality, and sparsity. By using fine-grained reductions, we can more precisely compare the relative difficulty of different problems in P. This approach provides a more detailed and nuanced understanding of algorithmic complexity and can be particularly useful in addressing complex problems that have practical applications in fields such as bioinformatics, optimization, cryptography, machine learning, and artificial intelligence.
The history of fine-grained complexity is relatively short. The first program on fine-grained complexity was organized by the Simons Institute for the Theory of Computing and held at the University of California, Berkeley in 2015. In the intervening decade, various related workshops have been held, and fine-grained complexity theory has developed into a widely applicable tool with many interesting directions including extensions to dynamic graph algorithms, hardness of approximation, compressed data, external memory algorithms, and many more.
The Special Focus on Fine-grained Complexity aims to bring together researchers in fine-grained complexity with the combined goals of 1) consolidating and invigorating efforts to address the big important problems in the area and 2) equipping a large cohort of graduate students with the tools and insights of fine-grained complexity. The Special Focus launches in July 2024 with a Tutorial on Fine-grained Complexity for graduate students and runs for three years through June 2027. Adding to the Tutorial are a set of four workshops and a small, targeted visitor program. Each Special Focus workshop addresses an overarching application area or technique in fine-grained complexity. Application areas to be addressed include graph problems, string problems, and geometric problems, while the techniques highlighted include developing algebraic tools for fine-grained complexity and developing (tools for) the topic of hardness of approximation in P. Each workshop seeks to outline long and short term goals within the topic through discussion of current research directions that highlight the most compelling open problems.
Special Focus Organizer:
- Karthik C. S., Rutgers University
DIMACS Focal Point Person: Tamra Carpenter, DIMACS
Send an email to the organizers: fine-grained-complexity (at) dimacs.rutgers.edu.
Opportunities to Participate:
- Calendar of Events: A variety of workshops and other events are part of the Special Focus.
- Research Visits: The Special Focus has a modest amount of funds to support associated research visits. Visits can be hosted at Rutgers, at a DIMACS partner location, or any other location that is appropriate. For information on how to apply please email the organizers at the above email address.
- Graduate Student Support: Each workshop will reserve funds to support attendance by graduate students. Information on how to apply for such funds will be posted on each workshop's webpage roughly two months ahead of the event. Students interested in attending a workshop are encouraged to apply.
- Materials and Publications: We anticipate that activities of the Special Focus will be documented through slides and video of workshop presentations as well as research publications.
Join the Mailing List:
If you would like to receive updates and announcements about future activities, you can join the mailing list for the Special Focus on Fine-grained Complexity by contacting the DIMACS Publicity Coordinator and asking to be placed on the SF_FGComplexity mailing list.
Sponsorship:
The DIMACS Special Focus on Fine-grained Complexity Complexity is supported by DIMACS and its partners, and by the National Science Foundation under grant number CCF-2422558.