Algorithmic theory of new data models – AlgoriDAM

We used tools from mathematics and theoretical computer science: probability, graphs, streaming, algorithms.

One may note in particular one PhD thesis, by Simon Mauras, on the probabilistic modeling and analysis of stable marriage. But there are also numerous algorithmic works, on graphs, approximation algorithms, streaming online and multistage algorithms, and testing and uncertainty, resulting in publications in top-level venues.

We have 3 postdocs starting in 2022 and expect great collaborations with them.

24 articles and preprints including:
- APPROX/RANDOM, FOCS, ESA (4), ISAAC, SODA, FODS, ICALP, FCT, STOC, ICALP, WAOA, SPAA, ITCS, Eurocomb (2),
- JCSS, Op Res Let, Algorithmica, Electronic J. Combinatorics (2)
- 1 preprint

We will develop the theory of algorithms for massive, erroneous and dynamic data, by focusing on three settings and on the interplay between them: (1) Massive data (e.g., the data is too large to fit in memory), in particular local computation models and streaming; (2) Noisy data (e.g. the data cannot be reliably accessed and hence observed with error, or noise), in particular with probabilistic noise, intervals of uncertainty, and property testing; (3) Dynamic data (e.g, the data evolves constantly), in particular dynamic data streams, evolving data, and online computing with recourse. We will use algorithmic and mathematical tools such as: randomization, information theory, communication complexity, or dynamic data structures.