Kapralov Lab

Research focus

ERC Starting Grant · 2017

Sublinear Algorithms for Modern Data Analysis

Designing efficient algorithms for fundamental computational tasks as well as understanding the limits of tractability has been the goal of computer science since its inception. Polynomial runtime has been the de facto notion of efficiency since the introduction of the notion of NP-completeness. As the sizes of modern datasets grow, however, many classical polynomial time (and sometimes even linear time) solutions become prohibitively expensive. This calls for sublinear algorithms, i.e. algorithms whose resource requirements are substantially smaller than the size of the input that they operate on. We propose to design a toolbox of powerful algorithmic techniques with sublinear resource…

From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.