Opendata, web and dolomites


Sublinear Algorithms for Modern Data Analysis

Total Cost €


EC-Contrib. €






Project "SUBLINEAR" data sheet

The following table provides information about the project.


Organization address
address: BATIMENT CE 3316 STATION 1
postcode: 1015

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Switzerland [CH]
 Total cost 1˙473˙175 €
 EC max contribution 1˙473˙175 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2017-STG
 Funding Scheme ERC-STG
 Starting year 2018
 Duration (year-month-day) from 2018-03-01   to  2023-02-28


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 


 Project objective

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 requirements that will form the theoretical foundation of large data analysis, as well as develop a nuanced runtime, space and communication complexity theory to show optimality of our algorithms. Specifically, we propose to:

1. design an algorithmic toolkit for sublinear graph processing that will form the basis of large scale graph analytics; 2. design a new generation of sublinear algorithms for signal processing that will become the method of choice for a wide range of applications; 3. develop a far-reaching set of techniques for lower bounding runtime, space and communication complexity of sublinear algorithms.

The problems that we propose to solve are among the most fundamental algorithmic questions on the forefront of the rapidly developing algorithmic theory of large data analysis, which has been the focus of an extensive body of work in the research community. The algorithms and complexity theoretic results that we propose to design will cut at the core of fundamental computational problems and form the theoretical foundation of computing with constrained resources.


year authors and title journal last update
List of publications.
2019 S. Assadi, M. Kapralov, S. Khanna
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
published pages: , ISSN: , DOI: 10.4230/lipics.itcs.2019.6
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 2019-11-08
2020 M. Elias, M. Kapralov, J. Kulkarni and Y. T. Lee
Differentially Private Release of Synthetic Graphs
published pages: , ISSN: , DOI:
SIAM Symposium on Discrete Algorithms (SODA 2020) 2019-11-08
2019 A. Amrollahi, A. Zandieh, M. Kapralov, A. Krause
Efficiently Learning Fourier Sparse Set Functions
published pages: , ISSN: , DOI:
Thirty-third Conference on Neural Information Processing Systems 2019-11-08
2020 T. D. Ahle, M. Kapralov, J. B. T. Knudsen, R. Pagh, A. Velingker, D. Woodruff and A. Zandieh
Oblivious Sketching of High-Degree Polynomial Kernels
published pages: , ISSN: , DOI:
SIAM Symposium on Discrete Algorithms (SODA 2020) 2019-11-08
2020 M. Kapralov, S. Mitrovic, A. Norouzi-Fard, J. Tardos
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
published pages: , ISSN: , DOI:
2020 M. Kapralov, A. Mousavifar, C. Musco, C. Musco, N. Nouri, A. Sidford, J. Tardos
Fast and Space Efficient Spectral Sparsification in Dynamic Streams
published pages: , ISSN: , DOI:
SIAM Symposium on Discrete Algorithms (SODA 2020) 2019-11-08
2019 Gamlath, Buddhima; Kapralov, Michael; Maggiori, Andreas; Svensson, Ola; Wajc, David
Online Matching with General Arrivals
published pages: , ISSN: , DOI:
IEEE Symposium on Foundations of Computer Science (FOCS 2019) 2019-11-07

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "SUBLINEAR" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "SUBLINEAR" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

SUExp (2018)

Strategic Uncertainty: An Experimental Investigation

Read More  

HyperBio (2019)

Vis-NIR Hyperspectral imaging for biomaterial quality control

Read More  


Dynamic Modeling of Labor Market Mobility and Human Capital Accumulation

Read More