Multivariate Algorithms: New domains and paradigms

The project concerns fundamental research in ICT, in particular within the fields of algorithms and complexity. The field of theoretical computer science is faced with a fundamental challenge: the predictions made by the theory do not match empirical observations. The objective of the proposed research is to address this fundamental problem by revising the foundations of theoretical computer science, changing how computational efficiency is measured in terms of the properties of the input data. In particular, we will establish multivariate algorithms as the standard approach to algorithm design and analysis. To reach the goals of this interdisciplinary research project, we will exploit cross-domain synergies and collaborate with the world leading scientists. Since computation permeates everything, the successful completion of our program will yield progress in all areas of science and technology, as well as in our daily lives. In 2018 and 2019 we develop the techniques and methods of multivariable algorithmic analysis. We succeed to obtain new algorithmic and complexity results for computational problems from several domains. All these results appear in prestigious international journals and conferences as well as in the open access repository of electronic preprints ArXiv. https://arxiv.org/search/cs?searchtype=author&query=Fomin%2C+F+V In 2020 and 2021, we extended the multivariate approach to the domains of AI and unsupervised machine learning.

The highlights of the results obtained within the project are: (a) New tools for designing efficient approximation schemes in planar and geometric graphs (b) Meta-theorems about efficient preprocessing (c) Lower bounds on the solvability of Integer Linear Programming (d) Developing multivariate algorithmic analysis for clustering problems (e) Novel multivariate algorithmic approach to the robustness of Principal Component Analysis.

The project concerns fundamental research in ICT, in particular within the fields of algorithms and complexity. The field of theoretical computer science is faced with a fundamental challenge: the predictions made by the theory do not match empirical observations. The objective of the proposed research is to address this fundamental problem by revising the foundations of theoretical computer science, changing how computational efficiency is measured in terms of the properties of the input data. In particular, we will establish multivariate algorithms as the standard approach to algorithm design and analysis. To reach the goals of this interdisciplinary research project, we will exploit cross-domain synergies and collaborate with the world leading scientists. Since computation permeates everything, the successful completion of our program will yield progress in all areas of science and technology, as well as in our daily lives.