Tag : Français

Substring Compression Problems

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.

Algorithmes pour des problèmes géométriques et topologiques

Dans une première partie, nous considérons le problème du démêlage de graphes sur les surfaces : étant donné un dessin d’un graphe sur une surface, éventuellement avec des croisements, nous devons supprimer tous les croisements en déformant le dessin continuement, ou affirmer correctement que ce n’est pas possible. Nous donnons les premiers algorithmes en temps polynomial pour ce problème. Pour ce faire, nous introduisons un nouveau type de triangulations de surfaces qui discrétisent les surfaces à courbure négative d’une façon meilleure que l’état de l’art. Sur ces triangulations, nous fournissons un analogue combinatoire des célèbres plongements barycentriques de Tutte.

Dans un cadre plus géométrique, nous donnons un nouvel algorithme efficace pour calculer une triangulation de Delaunay d’une surface abstraite plate par morceaux (une généralisation des maillages). Nous étudions également l’algorithme classique de bascule de Delaunay et prouvons, lorsque la surface est un tore plat, la première borne dans le pire cas qui soit opti- male à facteur constant près. Sur les surfaces hyperboliques, nous fournissons une implémentation de l’algorithme de bascule de Delaunay, collectée dans un package de la bibliothèque standard de géométrie algorithmique CGAL, et accompagnée d’outils de génération et de visualisation pratiques.

ENGLISH VERSION:

In a first part, we consider the problem of untangling graphs on surfaces: given a drawing of a graph on a surface, possibly with crossings, remove all crossings by deforming the drawing continuously, or correctly assert that this is not possible. We give the first polynomial time algorithms for this problem. To do so we introduce a new kind of triangulations of surfaces that discretize negative-curvature surfaces in a better way than the state of the art. On these triangulations, we provide a combinatorial analog of the celebrated barycentric embeddings of Tutte.

In a more geometric setting, we give a new efficient algorithm for computing a Delaunay triangulation of an abstract piecewise-flat surface (a generalization of meshes). We also study the classical Delaunay flip algorithm, and prove, when the surface is a flat torus, the first worst-case bound that is tight up to a constant factor. On hyperbolic surfaces, we provide an implementation of the Delaunay flip algorithm, collected in a package of the standard library of computational geometry CGAL, along with convenient generation and visualization tools.

Introduction to Geometric Algebra


L’algèbre géométrique, ou algèbre de Clifford, offre un cadre unifié pour représenter et manipuler des objets géométriques de toute dimension. Des objets les plus simples comme les scalaires et les vecteurs, jusqu’aux bivecteurs et aux entités de dimensions arbitraires, elle permet de capturer à la fois la magnitude et l’orientation grâce à des opérations comme le produit scalaire, le produit extérieur et le produit géométrique. Cette présentation introduit ces concepts fondamentaux à travers des exemples intuitifs en 2D et 3D. Elle se conclut par une ouverture vers des algèbres plus avancées, telles que PGA (Projective Geometric Algebra), CGA (Conformal Geometric Algebra) et CCGA (Conic Conformal Geometric Algebra), etc. , qui élargissent ce formalisme en permettant de représenter de façon unifiée les intersections, les transformations et les courbes de degré arbitraire



Geometric Algebra, or Clifford Algebra, provides a unified framework for representing and manipulating geometric objects of any dimension. From scalars and vectors to bivectors and higher-grade elements, it captures both magnitude and orientation through operations like the inner, outer, and geometric products. This presentation introduces these core concepts with intuitive examples in 2D and 3D. We conclude by opening the door to more advanced geometric algebras—such as Projective Geometric Algebra (PGA), Conformal Geometric Algebra (CGA), and Conic Conformal Geometric Algebra (CCGA)—which extend the power of this formalism to model intersections, transformations, and arbitrary-degree curves in a unified way.



Dichotomie et chemins dans les graphes de révisions

Les systèmes de contrôle de version utilisent de manière sous-jacente un graphe pour organiser les versions successives d’un projet. Néanmoins les algorithmes de graphe classiques peuvent se heurter aux spécificités des graphes de révision. D’une part, les graphes reçoivent très fréquemment des nouveaux sommets et des informations pré-calculées peuvent devenir obsolètes à chaque commit. D’autre part, deux utilisateurs différents peuvent avoir une vue différente sur le graphe, y compris sur les sommets qu’ils ont en commun.
Nous proposons une approche dichotomique donnant une stratégie de découpe de profondeur logarithmique du graphe. Nous appliquons cette méthode à deux problèmes: (1) la comparaison d’annotations entre deux vues d’un même graphe, et (2) la recherche de chemin dans le graphe. Pour le second problème, nous présentons également un algorithme basé sur la décomposition du graphe en chaînes totalement ordonnées.

Cette présentation est basée sur plusieurs travaux en collaboration avec Pierre-Yves David , Florian Horn and Euxane Tran-Girard :

https://hal.science/hal-04929088v1

https://hal.science/hal-04778558v1

Contributions aux Réseaux Terrestres et Véhiculaires Assistés par Drones

Cette présentation, qui est effectuée en anglais, se concentre sur trois axes majeurs relatifs aux réseaux terrestres et véhiculaires assistés par UAV. Le premier axe traite du routage assisté par UAV pour les réseaux VANET. Les véhicules en milieu urbain peuvent rencontrer des difficultés de connectivité, notamment en raison de leur mobilité rapide et des zones de couverture intermittentes. Dans ce contexte, des protocoles comme U2RV, qui utilise des UAVs comme relais aériens, sont proposés pour améliorer la connectivité en reliant les véhicules entre eux et aux infrastructures. Ces protocoles permettent de réduire la latence et d’améliorer la sécurité routière, en particulier dans les zones urbaines densément peuplées.

Le deuxième axe explore les applications des UAVs dans les réseaux VANET, notamment pour l’amélioration de la gestion des urgences et la communication dans des zones difficiles d’accès. Les UAVs jouent ici un rôle crucial en offrant une vue aérienne des zones urbaines et en permettant de guider efficacement les véhicules d’urgence grâce à un traitement en temps réel des données de circulation. Ces systèmes permettent de réagir rapidement en cas d’accident, de réduire les délais d’intervention et d’optimiser les parcours des services de secours, ce qui améliore considérablement l’efficacité des interventions d’urgence.

Enfin, le dernier axe porte sur les UAVs alimentés sans fil dans les réseaux terrestres. Cette technologie permet aux UAVs de maintenir leur opérationnalité pendant de longues périodes en utilisant des stations mobiles de recharge, telles que des UGVs (véhicules terrestres non habités), qui fournissent de l’énergie en temps réel aux UAVs en vol. Ce système est essentiel pour les missions prolongées, notamment dans les réseaux IoT, où la collecte de données en continu est primordiale. L’objectif est d’optimiser la gestion de l’énergie, en réduisant la consommation des UAVs tout en assurant une couverture optimale et une actualisation constante des données collectées.

Dans la suite de cette présentation, nous aborderons également des perspectives futures pour ces technologies. Ces perspectives incluent l’amélioration de l’efficacité énergétique, la gestion des grandes flottes de UAVs dans des environnements urbains denses et l’optimisation des protocoles de routage pour répondre aux besoins croissants en matière de connectivité et de sécurité.

Locality via Alternation?

In this talk, I will show how logic and automata theory can help research in distributed computing.

I will start with an attempt to use logic to extend standard complexity theory to the distributed setting. It turns out that several classical concepts generalize well, including the polynomial hierarchy (and hence the complexity classes P and NP), the Cook-Levin theorem (which identifies Boolean satisfiability as a complete problem for NP), and Fagin’s theorem (which characterizes NP as the problems expressible in existential second-order logic). But perhaps more surprisingly, separating complexity classes becomes easier in the general case: when extended to multiple computers, the polynomial hierarchy is provably infinite, while it remains notoriously open whether the same holds in the case of a single computer.

In the second part of the talk, I will use the previous results to address a central question in distributed computing: which problems are purely local, which problems are inherently global, and which problems lie between these extremes? The idea will be to measure locality using quantifier alternation, the key concept underlying the polynomial hierarchy.

The talk is based on my paper “A LOCAL View of the Polynomial Hierarchy”.
– Proceedings version: https://doi.org/10.1145/3662158.3662774
– Full version: https://arxiv.org/abs/2305.09538

Stable Value in Java

Java 25 introduira bientôt une nouvelle API appelée Stable Value, répondant au défi subtilement complexe de l’initialisation paresseuse de valeurs constantes.

L’API Stable Value repose sur trois concepts fondamentaux : l’initialisation ne se produit que lorsque c’est nécessaire, chaque valeur n’est initialisée qu’une seule fois et le résultat sauvé pour les utilisations ultérieures.

Bien que le concept semble simple, en pratique, implémenter une initialisation paresseuse, thread-safe et économe en ressources des constantes est loin d’être facile.

Après un bref rappel sur le fonctionnement des cœurs des CPU, nous explorerons les différentes approche de l’initialisation paresseuse et leurs limites. Nous passerons en revue les meilleures pratiques actuelles recommandées dans le livre Effective Java et expliquerons l’API Stable Value proposée pour Java 25 avec ses avantages et inconvénients.

Rejoignez moi pour découvrir comment cette nouvelle API résout un défi épineux de la programmation en Java.

Recent advances in exact algorithms for the Multiagent Path Finding problem.

In the Multiagent Path Finding problem, we focus on efficiently finding non-colliding
paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time).
We propose a systematic algorithmic study of this problem under the parameterized complexity framework.

We present a plethora of hardness results, which align with many heuristics used for this problem, whose running time could potentially be improved based on our fixed-parameter tractability results. In particular, we show that an exact solution to MAPF cannot be computed efficiently, unless P=NP, even if we consider very restrictive settings such as a bounded k, bounded l, or networks with star-like topologies (bounded vertex cover number) or even trees with 11 leaves. On the positive side, we present efficient algorithms for instances with bounded  k + l, k plus the diameter of the graph G, or networks with highly centralized topologies (bounded distance to clique). This parameter is significant as it mirrors real-world
networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only a few peripheral nodes.

These results were obtained by collaborating with Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler and Tung Anh Vu, and were presented in AAAI’24 and AAAI’25.

Evaluation de l’architecture de communication pour la mobilité connectée et automatisée et coopérative (CCAM)

Les Systèmes de Transport Intelligents Coopératifs (C-ITS) jouent un rôle fondamental dans le développement de la mobilité connectée, automatisée et coopérative (CCAM). Ces systèmes permettent une communication entre l’infrastructure routière, les véhicules et entre véhicules eux-mêmes, ce qui améliore la sécurité routière, la gestion du trafic, l’expérience des usagers, et favorise les économies d’énergie. Cependant, avec l’émergence des véhicules automatisés et des cas d’usage plus complexes, les exigences en matière de latence, bande passante et consommation de ressources ont considérablement augmenté.
Cela conduit à une remise en question de l’architecture de communication actuelle, notamment en France, où l’architecture C-ITS hybride combine les technologies ITS-G5 et cellulaires afin de relier les opérateurs routiers aux véhicules.
Dans ce contexte, l’évaluation des systèmes de communication, et plus particulièrement des technologies de communication, devient une nécessité afin de mieux répondre aux exigences de performance de ces services coopératifs. Dans le cadre de cette présentation, je propose une étude d’évaluation de ces technologies de communication, ainsi que des perspectives de recherche dans la continuité de ces travaux.

Middle orders : all distributive lattices between weak and Bruhat orders

The weak order and Bruhat order are well-known posets on permutations, the weak order being a lattice which is contained in the Bruhat order.
Recently a new distributive lattice on permutations called „middle order“ was discovered, containing the weak order and contained in the Bruhat order.
We generalize this result by constructing C_{n-1} distributive lattices on permutations of size n with the same property, using a simple bijection between permutations and ideals of posets.
We then show these lattices are the only distributive lattices between weak and Bruhat orders, and we also consider generalizations of middle orders in other Coxeter groups.

IMPORTANT: Le séminaire doctorant est réservé au non-permanents du laboratoire. Cependant, n’hésitez pas à contacter l’oganisateur.ice si vous êtes permanent et que le sujet vous intéresse !