Demi Journées du Pôle Calcul

---

Orateur : Édouard Bonnet
Titre : Graph decompositions and their algorithms
Résumé : Through simple examples, we take a representative glimpse at forty years of using width parameters for algorithmic purposes. The talk will be biased towards revisiting this history through the lens of contraction sequences, which are at the basis of the recently introduced twin-width. 

---

Orateur : Karoliina Lehtinen
Titre : Un peu de non-déterminisme peut aller loin: un aperçu des automates déterministes en histoire
Résumé : Le non-déterminisme permet surement à votre modèle d’automate préféré plus expressif, ou du moins plus succinct que le déterminisme. Cela se fait généralement au au prix d’une complexité algorithmique plus importante. Les classes d’automates intermédiaires, entre déterministes et non-déterministes, présentent des compromis intéressants en ce qui concerne l’expressivité, la succincté et les propriétés algorithmiques.

Les automates déterministes en histoire sont des automates non-déterministes dans lesquels les choix non-déterministes peuvent être faits sans connaître le futur du mot d’entré. Ils combinent une partie de la succincté et de l’expressivité des automates non déterministes avec certaines des propriétés algorithmiques utiles des automates déterministes. En particulier, les jeux avec des conditions gagnantes données par des automates déterministes en histoire ont tendance à être plus simples à résoudre que les jeux dont les conditions de gain sont non-déterministes.

Dans cet exposé, je donnerai une vue d’ensemble des automates déterministes en histoire, de leur relation avec divers problèmes de synthèse et des développements récents dans le domaine pour différentes classes d’automates.

Orateur : Nathan Lhote
Titre : Minimisation des transductions rationnelles
Résumé : La notion d’automate minimal (ou de monoïde syntaxique) fournit pour les langages réguliers un objet canonique qui capture beaucoup de propriétés intrinsèques d’un langage. Par exemple le théorème de Schützenberger nous dit qu’un langage est définissable en logique du premier ordre FO[<] si et seulement si son automate minimal est sans compteur. Depuis de nombreux résultats similaires ont été obtenus, faisant des liens entre expressivité dans une certaine logique et propriété de l’automate minimal.

Un transducteur est un automate équipé de sorties. Contrairement au cas des langages, les transducteurs ne sont pas toujours déterminisables. Pour les transducteurs, il n’existe certes pas d’automate minimal mais on montre qu’il existe un nombre fini de bimachines (modèle de calcul introduit par Schützenberger et étudié par Eilenberg) qui capturent (dans le même sens que l’automate minimal pour les langages) les propriétés d’une transduction.

---

Orateur : Alessia Milani (LIS)
Titre : Concurrent Counters with Polylogarithmic Step Complexity
Résumé : Shared data objects are an essential abstraction in distributed computing, as they provide a consistent interface for multiple processes to interact via shared data. Linearizability is the main consistency criterion that formalizes the correctness of shared object implementations. Linearizable shared objects are intuitive to use, but they can be expensive to implement. 

In this talk, I will consider a widely-used shared object, the counter. I will present a fundamental lower bound on the worst-case complexity of fault-tolerant implementations of counters and two ways of circumventing it. In particular,  in 2000, Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects, including counters. In 2012, Aspnes, Attiya and Censor-Hillel observed that the lower bound holds only when numerous operations are applied to the object and does not rule out the possibility of obtaining algorithms whose step complexity is sub-linear when the number of operations is bounded. 

We recently prove that there exists deterministic counters implementations with sub-linear amortized step complexity regardless of how many operations are performed on the object. This is a joint work with Mirza Ahad Baig, Danny Hendler and Corentin Travers 

The talk will be self-contained.

---

Orateur : Eloi Perdereau (LIS)
Titre : Accords Approchés et Asymptotiques pour les Adversaires de Message
Résumé : En calculabilité des systèmes distribués, les problèmes du Conensus et de l’Accord k-Ensembliste sont beaucoup étudiés car permettent de mettre en valeur des aspects fondamentaux des modèles. L’objet de notre travail est de proposer et d’étudier des relaxations du problème de l’Accord k-Ensembliste, sous l’angle de l’approximation géométrique de valeurs, à l’instar du Consensus Approché. Nous proposons deux nouveaux problèmes : l’Accord k-Convexe Approché et l’Accord k-Convexe Asymptotique, et étudions leur calculabilité pour des algorithmes de moyennes.

Le modèle distribué est celui des adversaires de message qui se base sur des séquences de graĥes dynamiques définissant les exécutions. Les scénarios considérés sont clos par suffixes et ont des comportements de récurrence bornée soit par l’apparition des arcs (BRec et FRec), soit par l’influence de certains sommets sur les autres (BISC et FISC). Ces adversaires forment une hiérarchie de fait et nous allons montrer que ces deux problèmes permettent de les séparer du point de vue de la calculabilité distribuée.

Orateur : Dmitry Sokolov (LORIA)
Titre : How to compute locally invertible maps
Résumé : Mapping a triangulated surface to 2D plane (or a tetrahedral mesh to 3D space) is the most fundamental problem in geometry processing. The critical property of a good map is a (local) invertibility, and it is not an easy one to obtain. We propose a mapping method inspired by the mesh untangling problem. In computational physics, untangling plays an important role in mesh generation: it takes a mesh as an input, and moves the vertices to get rid of foldovers. In fact, mesh untangling can be considered as a special case of mapping, where the geometry of the object is to be defined in the map space and the geometric domain is not explicit, supposing that each element is regular. This approach allows us to produce locally invertible maps, which is the major challenge of mapping. In practice, our method succeeds in very difficult settings, and with less distortion than the previous work, both in 2D and 3D.

---

Orateur : Corentin Travers (LABRI)
Titre : Synchronous t-Resilient Consensus in Arbitrary Graphs
Résumé : We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.

Our lower bound technique is inspired by the topological techniques for distributed computing. It is similar to the connectivity analysis of the protocol complex, the structure of states at the end of executions of an algorithm after a certain number of rounds. However, instead of working with the protocol complex, we consider an information flow directed graph version based on failure patterns.

Joint work with Armando Castaneda, Pierre Fraigniaud, Ami Paz, Sergio
Rajsbaum, and Matthieu Roy

---

Orateur : Victor Chepoi (LIS)
Titre : 1-safe Petri nets and special cube complexes
Résumé : In the talk, I will explain the following bijection between 1-safe Petri nets and finite special cube complexes: the event structures arising as unfolding of 1-safe Petri nets are exactly the event structures whose domains arise as principal filters of the universal cover of a finite 1-safe Petri net.

This can be viewed as a positive answer to the (disproved) conjecture by Thiagarajan that the event structures arising as unfolding of 1-safe Petri nets are exactly the regular event structures. If the time permits, I will give some (positive and negative) applications of this bijection.

Joint work with Jérémie Chalopin.

Orateur : Catuscia Palaminessi
Titre : A new mechanism for distributed Differential Privacy
Résumé : Differential Privacy (DP) is one of the most successful proposal to protect the privacy of the sensitive data while preserving their utility. In this talk, we will briefly introduce the DP framework, and then present a new proposal for a mechanism to implement DP in the distributed case, namely in a scenario in which the data collections are distributed across different organizations, which do not wish to disclose the original data but only their sanitized version, and still benefit from the advantages of combining the information coming from different sources. The mechanism we propose is particularly suitable for the application of a variant of the statistical Expectation-Maximization method, thanks to which the utility of the original data can be retrieved to an arbitrary degree of approximation, without affecting the privacy of the original data owners. 

Orateur : Adrien Varet
Titre : Utilisation de la programmation par contraintes pour résoudre des problématiques liées aux benzénoïdes
Résumé : Les benzénoïdes sont une sous-famille des hydrocarbures (molécules uniquement constituées d’atomes de carbone et d’hydrogène) dont les atomes de carbones forment des hexagones. Ces molécules sont beaucoup étudiées en chimie théorique. En effet, il existe un certain nombre de problèmes relatifs aux benzénoides dans différents domaines. Dans cette présentation, on se propose de se pencher sur deux problématiques en particulier, qui sont être capable de générer des structures de benzénoïdes ou calculer l’aromaticité locale d’un benzénoïde donné. Calculer l’aromaticité locale d’un benzénoïde revient à attribuer une énergie à chacun de ses hexagones qui est induite par les déplacements de ses électrons. A l’heure actuelle, la méthode la plus utilisée pour faire ce calcul (appellée NICS) requiert des calculs de chimie quantique et est extrêmenent coûteuse. Dans cette présentation, j’aborderais dans un premier temps une méthode utilisant la programmation par contraintes capable de générer l’ensemble de structures de benzénoïdes répondant à un certain nombre de de propriétés (qui peuvent être chimiques ou structurelles). Dans un second temps, je présenterais un algorithme utilisant la programmation par contraintes capable de calculer l’aromaticité locale d’un benzénoïde donné.