Fine-grained and Parameterized Complexity Today (FPcT)

One of the major achievements of computational complexity theory is differentiating between problems that can be solved efficiently and those that are intractable, based on concepts like NP-hardness. Fine-Grained Complexity aims to further categorize efficiently solvable problems according to their precise running time, relying on popular conjectures such as the Strong Exponential Time Hypothesis (SETH), All-Pairs Shortest Paths (APSP), and Boolean Matrix Multiplication. In recent years, there has been significant progress in Fine-Grained Complexity that has helped explain the lack of major advancements in various long-standing algorithmic challenges while revealing deep connections among numerous fundamental computational problems.

The concept of computational (worst-case) hardness, whether it involves NP-hardness or hardness within a fine-grained spectrum, encourages the identification of parameters of the instance that influence the time an algorithm requires. A key objective is to overcome the hardness barrier for instances with small parameter values. Parameterized Complexity is the study of the behavior of algorithms in terms of these parameters.

This workshop will concentrate on the intersection of Fine-Grained and Parameterized Complexity. It aims to explore how different natural parameters affect fine-grained hardness in both traditional and new problems and to strengthen the connections between algorithm development and lower bounds.

 Organisational Plan

The workshop will be run in the style of a Dagstuhl workshop, with both talks as well as time for discussion and collaboration. Full participation in the workshop is by invitation only. Most of the local logistics will be covered by the NUS School of Computing.

We expect the participants to cover their own costs (travel and accommodation). If you need travel support, please let us know. Depending on the availability of funds and the number of requests, we might be able to provide some support. Additionally, we are working on arranging some less expensive accommodation options, at least for the student participants; once available, we will let you know.