# Journée du pole ASD ## Schedule January 20 2026 Amphi Turing - 13h-13h40 Graphes (Giannos Stamoulis) - 13h45-14h25 Combi (Zoé Varin) break - 15h-15h40 Algo (Adrian Vladu) - 15h45-16h25 Distribué (Isabella Ziccardi) - 16h30 Galette ## Abstracts ### Graphes - Title From Graphs and Algorithms to Logic (and back) - Speaker Giannos Stamoulis - Abstract In this talk, we discuss different logics on graphs and how they are connected to graph classes in algorithmic and structural terms. The algorithmic part is understood via the model checking problem, while the structural one is a logic-based way of (re)defining graph classes. This approach provides a unified and robust framework for understanding the tractability of wide families of graph problems and obtaining new results. ### Combi - Title A probabilistic reinforcement-learning algorithm to find shortest paths/Un algorithme probabiliste d'apprentissage par renforcement pour la recherche de plus courts chemins sur un graphe - Speaker Zoé Varin - Abstract We study a reinforcement-learning algorithm inspired by ants that communicate with pheromones. We consider a weighted finite graph G, with two nests N1 and N2 and a source of food F. At each step, an ant : 1) starts from a (random) nest N1 or N2 and does a weighted random walk on G, stopped when it first hits the source of food F, and 2) it deposits pheromones (i.e. it adds 1 to the corresponding edges' weights) on its way back, taking the path obtained by taking its forward trajectory backwards in time and erasing useless loops. For technical reasons, we restrict ourselves to the case when the graph is a triangle-series-parallel graph, that is, the graph obtained by considering a triangle between the two nests and the source of food, and replacing each edge by a series-parallel graph. In this setting, we are able to prove that this ants process converges and to describe its limit. In this talk, I will present this result and the main tools we use, namely stochastic approximation techniques, comparison with Pólya urns, and combinatorial arguments. Joint work with Cécile Mailler. On étudie un processus d'apprentissage par renforcement, pour la recherche de plus courts chemins dans un graphe, dans lequel des fourmis partent d'un nid (aléatoire, N1 ou N2) et font une marche aléatoire (pondérée par les poids des arêtes) jusqu'à une source de nourriture F. À leur retour, elles déposent des phéromones, c'est-à-dire renforcent les arêtes (en ajoutant 1 à leur poids) appartenant au chemin aller auquel on a enlevé les boucles inutiles. Ce modèle a déjà été étudié sur divers graphes dans le cas où le nid est déterministe, notamment les graphes séries-parallèles, mais aussi pour d'autres politiques de renforcements (articles de Kious, Mailler et Schapira). Nous étudions le cas à deux nids, dans des graphes obtenus en joignant trois graphes séries-parallèles pour former un triangle. 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, et quelques résultats sur les approximations stochastiques. La présentation se basera sur un travail en commun avec Cécile Mailler. ### Algo - Title TBA - Speaker Adrian Vladu - Abstract ### Distribué - Title Leader Election under Weak Communication - Speaker Isabella Ziccardi - Abstract In this talk, I will discuss distributed leader election algorithms in weak communication models such as the beeping model and the stone-age model. Unlike most previous works, our algorithm operates with only six states, does not require unique identifiers, and makes no assumptions about prior knowledge of the network’s size or topology. We show that, under our randomized protocol, the system almost surely converges to a configuration in which a single node enters the leader state, in O(D² log n) rounds, where D is the network diameter. Moreover, if an approximation of D is known, the convergence time can be improved to O(D log n). The algorithm is not self-stabilizing, as it requires all nodes to start from the same initial state. I will also present ongoing work on a generalization of the algorithm in the state-based computation model, aiming to achieve a self-stabilizing solution.