Michael Kapralov awarded an ERC Starting Grant

Out of 1339 grant applications in Physical Science and Engineering, only 177 (13.2 %) received a starting grant for 2018. 11 (6.2%) of those selected were from Swiss Universities and Research Institutes and five (45.4%) directly from EPFL. The objective of the ERC grant scheme is to encourage high- quality research in Europe through competitive funding and to support investigator-driven frontier research. Proposals are evaluated on the basis of excellence as the sole criterion by selected international peer reviewers.

Professor Kapralov, who joined IC School in 2016 and leads the Theory of Computation Laboratory 4, aims to design efficient algorithms for fundamental computational tasks, as well as understand the limits of tractability, one of the key goals of computer science since its inception. He proposes to develop sublinear algorithms, i.e. algorithms that use resources smaller than the size of their input, to operate on modern large datasets, since classical polynomial and even linear runtime solutions become prohibitively expensive on such inputs.

Michael Kapralov’s project will focus on designing a toolbox of powerful algorithmic techniques with sublinear resource requirements, which will form the theoretical foundation of large data analysis. At the same time he also aims to develop a nuanced runtime, space and communication complexity theory to demonstrate the efficiency of these algorithms.

The problems he proposes to address are essential to the rapidly developing algorithmic theory of large data analysis, at the core of fundamental computational problems, and form the theoretical foundations of computing with constrained resources.

Reference

Sublinear Algorithms for Modern Data Analysis, 2018 ERC Starting Grant