New Horizons of Parameterized Complexity

Parameterized Complexity (PC) provides an approach to moving beyond classic worst-case analysis of algorithms by focusing on multivariate algorithms whose performance is influenced by several parameters beyond input size. While it has been successful in various algorithmic domains, particularly those involving discrete objects like graphs, sets, matroids, or Boolean formulas, PC remains underutilized in areas involving geometric and algebraic objects such as points, vectors, linear spaces, or matrices. This project seeks to revolutionize the PC field by developing novel multivariate algorithms for continuous optimization problems involving such objects. The performance of these algorithms—whether measured by approximation ratio, probability error, or running time—is highly sensitive to multiple parameters.The main challenge in advancing parameterized complexity to these new domains is the need for suitable algorithmic and complexity tools. To address this challenge, the NewPC project proposes to revisit and revise fundamental methods for handling geometric and algebraic objects—such as dimension reduction, sampling, sketching, clustering, and coresets—through the conceptual questions of PC, including determining proper parameterization, quantifying the distance from triviality, and identifying when kernelization is possible.In short, the proposed Research Program can be summarized as:Questions of PC + Geometric Methods = New HorizonsThe proposed research will open new horizons in parameterized complexity by- Advancing multivariate approximation and lossy kernelization, both emerging areas within parameterized complexity.- Establishing multivariate algorithmic analysis as the standard tool for designing provably correct and efficient algorithms in domains such as computational geometry, machine learning, robust statistics, and optimization—areas where the classical worst-case algorithmic analysis often falls short.