Lieu : Salle de séminaire 4B125 (bâtiment Copernic)

Cet exposé est composé de deux parties. Dans la première, je présente un nouveau cadre d’étude de l’erreur de généralisation des algorithmes d’apprentissage statistique, à travers un nouveau prisme de compressibilité de taille variable des algorithmes que j’introduis.

Dans ce cadre, l’erreur de généralisation d’un algorithme est liée au taux de compression de ses données d’entrée. Je montrerai que : (i) cela permet d’obtenir des bornes qui dépendent de la mesure statistique empirique des données plutôt que de leur distribution inconnue, (ii) que ces bornes englobent et améliorent plusieurs bornes existantes de type PAC-BAYES, ou obtenues par approche théorie de l’information comme celle de Xu-Raginsky ou encore fondées sur la dimension intrinsèque de la structure fractale sous-jacente de l’algorithme, révélant ainsi le caractère unificateur de l’approche. Il sera aussi montré que l’on peut utiliser ce cadre pour développer de nouvelles bornes plus fines sur la généralisation.

Dans la seconde partie de l’exposé, j’aborde la question importante du rapport entre pouvoir de généralisation et faculté de mémoire des algorithmes d’apprentissage statistique, question qui est encore à élucider.

En effet, l’intuition selon laquelle les bons algorithmes devraient extraire uniquement les informations pertinentes et écarter les informations superflues, intuition étayée par certains travaux théoriques, est remise en question par le succès retentissant des réseaux de neurones profonds sur-paramétrés modernes. Je montrerai comment le cadre de compressibilité introduit dans la première partie de l’exposé permet de déterminer si la mémorisation est une composante nécessaire a la généralisation, comme cela a été récemment affirmé dans certains travaux.

• Data-dependent generalization bounds via variable-size compressibility, IEEE Transactions on Information Theory, vol. 70, no. 9, p. 6572-6595, Sept. 2024, disponible sur https://arxiv.org/abs/2303.05369,
• Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization, NeurIPS 2025, disponible sur https://arxiv.org/abs/2510.23

The chromatic number of a graph is the minimum number of colours one needs to colour its vertices so that the endpoints of every edge receive distinct colours. This metric, introduced nearly two centuries ago, has since played a central role in graph theory and has found numerous practical applications.

A natural question in structural graph theory is how the chromatic number constrains the structure of graphs. One prominent example is the Gyárfás-Sumner conjecture, which aims to characterize the local structure of graphs with arbitrarily large chromatic number. Although this question may sound like yet another structural graph theorist’s favourite refrain (« how does metric interact with graph structure? ») we will explain why it is genuinely well motivated and how one is naturally led to the Gyárfás-Sumner conjecture.

We then show how similar lines of reasoning lead to similarly flavoured conjectures for other combinatorial objects, in particular directed graphs. We conclude by presenting recent advances towards this directed analogue of the Gyárfás-Sumner conjecture.

This talk features joint works with Pierre Aboulker, Pierre Charbit, Luis Kuffner, Rafael Steiner and Stephan Thomassé.

On étudie un processus d’apprentissage par renforcement, inspiré par les fourmis, qui communiquent à l’aide de phéromones. On considère un graphe G, avec deux nids (des sommets, N1 et N2) et une source de nourriture (un autre sommet, F). À chaque étape, une fourmi : 1) part d’un nid (aléatoire, N1 ou N2) et réalise une marche aléatoire (pondérée par les poids des arêtes) jusqu’à une source de nourriture F ; puis 2) à son retour, elle dépose des phéromones, c’est-à-dire renforce les arêtes (en ajoutant 1 à leur poids) appartenant au chemin aller auquel on a enlevé les boucles inutiles.

Pour des raisons techniques, nous étudions le cas des graphes séries-parallèles en triangle, c’est à dire des graphes obtenus en remplaçant chaque arête du triangle N1 N2 F par un graphe série-parallèle. On montre que les poids des arêtes (normalisés) convergent, vers des variables aléatoires nulles si les arêtes associées n’appartiennent pas à un plus court chemin d’un sommet de {N1, N2, F} à un autre.

Nous présenterons plusieurs outils utiles pour prouver cette convergence, notamment la comparaison avec des processus d’urnes, des techniques d’approximations stochastiques et des arguments combinatoires.

La présentation se basera sur un travail en commun avec Cécile Mailler.

SIMD (Single Instruction, Multiple Data) instructions are a type of computer processor instruction that allows the same operation to be performed on multiple pieces of data at the same time. Typically, one can find all occurrences of a given byte value in a sequence of 16 bytes with a single instruction. When used effectively, this can greatly accelerate performance.

In this talk we explore some current SIMD versions of hash tables. For example, an idea is to build a table of size-16 buckets for the keys, each equipped with a 16-bytes word that contains a 1-byte fingerprint of the keys it contains: when looking for a key, one first checks with only one SIMD instruction if there are keys with the same fingerprint present in the bucket.

In a work that is currently in the writing phase, with Cyril Nicaud, we have successfully derived the mathematical equations that precisely describe the evolution of these tables as elements are inserted. Notably, we study the number of full-buckets (e.g., containing 16 keys). These solutions are not merely the functions resulting from the analysis of  standard hash tables multiplied by a constant factor. Instead, they are obtained through a probabilistic approach and are implicitly expressed as solutions of systems of differential equations. This relies on probabilistic techniques developed by Nicholas Wormald for studying dynamic random graphs.

This presentation explores vehicular ad hoc networks (VANETs) as a key component of intelligent transportation systems, enabling safer and more efficient road traffic through communication between vehicles and infrastructure. With the growing use of UAVs in urban environments, this work examines how vehicles and drones can cooperate to form a unified communication network. I introduce three routing approaches designed to improve inter‑vehicle communication in urban areas: a connectivity‑based routing method assisted by UAV supervision, a dual‑layer routing scheme separating ground and aerial communication, and a reactive routing strategy that predicts route expiration times. Simulation results highlight the strengths and limitations of these approaches and demonstrate their potential to enhance reliable end‑to‑end communication in VANETs.

Dans cet exposé, je ferai une courte introduction de la vectorisation, une technique qui exploite des instructions matérielles spécifiques, les instructions SIMD, afin d’accélérer le traitement de donnée par le processeur. La vectorisation est le plus souvent réalisée automatiquement par les compilateurs, mais elle devient difficile lorsque le calcul est par nature séquentiel et que le contrôle de flot dépend fortement des données.

Un cas emblématique de programmes peu ou mal vectorisés automatiquement est celui de l’exécution d’automates. Dans cet exposé, je présenterai des méthodologies pour vectoriser les automates, qui s’appuient sur des résultats classique et récent de théorie algébrique des automates ainsi que quelques application concrètes de ces méthodologies.

We study indexing data structures for substring compression problems.Given an input text \(T\), a substring compression problem for a compression scheme \(C\) and a query interval \([i..j]\) asks to compute the compressed form of the substring \(T[i..j]\) with respect to \(C\) — that is, to apply \(C\) to \(T[i..j]\), which we write as \(C(T[i\ldots j])\). While \(T\) and \(C\) are given in advance, the interval \([i\ldots j]\) is specified at query time.

This setting allows preprocessing \(T\) to facilitate efficient answers to substring compression queries under \(C\). Space- or time-optimal solutions are straightforward but impractical:

— A space-optimal solution applies \(C(T[i\ldots j])\) at query time, without any preprocessing (selecting the optimal implementation of \(C\) with respect to space).

— A time-optimal solution precomputes \(C(T[i\ldots j])\) for all text positions \(i, j\), but requires at least quadratic space and preprocessing time.

Here, optimal time refers to linearity in the size of the compressed output. Thus, a natural question arises: Can we build an index over \(T\) that supports substring compression queries with near-optimal query time and subquadratic space?

In this talk, we explore approaches for compression schemes \(C\) related to the Lempel–Ziv 78 factorization, and outline promising directions for future research.