Programming Languages, Algorithms and Structures: Models and Analysis (Plasma)
Project ANR Plasma 2026–2029
Contents
Description
All contemporary programming languages offer implementations of classical algorithms and classical data structures such as lists, hash tables, sorting, etc. These are basic building blocks that are used to develop larger programs. Efficient algorithms for dealing with such issues have been known for several decades, since the beginning of computing, often with several efficient variants proposed in the literature. When developers of a programming language choose to implement a particular algorithm, such as their generic array sort, they have a wide choice of solutions. In addition to the constraints of their language, they use various performance tests to guide their decision. Sometimes engineers innovate and go off the beaten track to propose completely new solutions.
In this project, we have brought together theoretical computer scientists with a shared interest in providing mathematical insight into real-world implementations. Beyond conducting detailed studies of key implementations, our primary goal is to develop a comprehensive theoretical framework for analyzing modern algorithms and data structures, which could be used to guide the evolutions of these algorithms. Additionally, we aim to create mathematical models that capture the key statistical properties of real-world data and validate these models against state-of-the-art implementations.
These studies will require us to simplify and formalize the various architectural mechanisms, for which we plan to propose relevant mathematical abstractions, ready to be used for studying other problems. We will also need to develop mathematical tools to conduct these analysis systematically, based on fields that have proven effective in this context: analytic combinatorics and discrete probabilities, areas in which the consortium members are specialists.
Funding
We have funding for a post-doc (one year) at the Université de Caen, a PhD at Université Gustave Eiffel, and three internships (3 months).