Février 2021 — Géométrie et Topologie du Calcul

« Introduction aux Algèbres Géométriques et leur aspects calculatoires » par Vincent Nozick (Université Eiffel)

Date : 18 février 2021
Orateur : Vincent Nozick
Titre : Introduction aux Algèbres Géométriques et leur aspects calculatoires
Résumé : Les Algèbres Géométriques constituent un ensemble d’outils intuitifs permettant de créer et de manipuler des objets géométriques. Longtemps entre les mains des mathématiciens, les informaticiens commencent à se les approprier et à entrevoir leur potentiel. Cet exposé s’inscrit dans cette démarche d’explication simple et commencera par une introduction sur les fondements de ces algèbres, à savoir les vecteurs, les multivecteurs ainsi que quelques produits sur ces multivecteurs. Nous verrons ensuite comment les utiliser pour résoudre efficacement et très simplement des problèmes de géométrie, en portant une attention particulière sur l’aspect calculatoire.

Janvier 2021 — Algorithmique et Structures Discrètes

« Quantum Distributed Computing  » par F. Le Gall (Nagoya University)

Date : 28 janvier 2021
Orateur : François Le Gall
Titre :
Quantum Distributed Computing
Résumé :
The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of both classical distributed computing and quantum computing, I will explain a result obtained with Frédéric Magniez (PODC 2018) on quantum distributed algorithms computing the diameter of the network. I will then briefly present more recent results (STACS 2019, PODC 2019) that show a separation between the computational powers of quantum and classical distributed algorithms in other models as well. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.

Novembre 2020 — Logique et méthodes formelles

« A new mechanism for distributed Differential Privacy  » par C. Palaminessi (INRIA Saclay)

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. 

Octobre 2020 — Intelligence Artificielle

« Utilisation de la programmation par contraintes pour résoudre des problématiques liées aux benzénoïdes » par A. Varet (LIS)

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é.

Juillet 2020 — Algorithmique et Structures Discrètes

« Graph Algorithms Through the Lens of Continuous Optimization » par Adrian Vladu

Orateur : Adrian Vladu
Titre : Graph Algorithms Through the Lens of Continuous Optimization

Résumé : Recent years have witnessed a surge in the development of fast graph algorithms based on continuous optimization primitives. Classically, graph algorithms have relied on purely combinatorial techniques. However, new ideas stemming from Scientific Computing and Machine Learning set forth an emerging theme of algorithm design via continuous optimization.

I will provide a tour through some of the techniques that underlie this theme, and show how they can be used to obtain fast algorithms for solving a range of fundamental problems such as: maximum flow, minimum cost flow, or optimal transport with entropic regularization.

This talk is based on arXiv:1902.06391, arXiv:2003.04863, and arXiv:1704.02310, but will be kept self-contained, and will assume no prior background in optimization.

Janvier 2020 — Modèles de calcul et Complexité

« Reachability in Vector Addition Systems is Not Elementary » par J. Leroux (LABRI)
« Locally definable vertex set properties are efficiently enumerable » par N. Creignou (LIS)
« Determinisation of Finitely-Ambiguous Copyless Cost Register Automata » par T. Lopez (LIS)

Orateur : J. Leroux (LABRI)
Titre : Reachability in Vector Addition Systems is Not Elementary


Orateur : N. Creignou (LIS)
Titre : Locally definable vertex set properties are efficiently enumerable


Orateur : T. Lopez (LIS)
Titre : Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Novembre 2019 — Intelligence Artificielle

« Dynamic epistemic logic for distributed computing – asynchrony and concurrency » par H. van Ditmarsch (LORIA)
« Non-normal modal logics: from models to proofs » par T. Dalmonte (LIS)
« Consistency Measures, Inconsistency Measures, and Mix Measures  » par V. Risch (LIS)

Orateur : Tiziano Dalmonte, LIS
Titre : Non-normal modal logics: from models to proofs
Résumé : Modal logics are applied in many different contexts, such as epistemic, deontic or temporal reasoning, and many others. In some of these contexts, the minimal normal modal logic K leads to counter-intuitive conclusions, such as the problem of logical omniscience or the problem of conflicting obligations, and gives rise to several paradoxes (Ross paradox, the paradox of gentle murder, …). For this reason, weaker modal logics — called non-normal – are considered. Non-normal modal logics are traditionally characterised by a possible world semantics with a neighbourhood function. In this talk I present an alternative semantics which is more natural for systems lacking monotonicity. I also present some new proof systems which have ‘good’ properties, moreover they provide a decision procedure of optimal complexity and allow one to construct countermodels for non-valid formulas. In the final part I present some open problems.


Orateur : Vincent Risch (LIS)
Titre : Consistency Measures, Inconsistency Measures, and Mix Measures (Preliminary Report)
Résumé : En collaboration avec Philippe Besnard Abstract: We give some insight into a preliminary attempt at investigating a notion of consistency measures. These would provide a consistency degree for any finite collection of logical formulas, on a par with the well-known notion of inconsistency measures, that aim at assigning degrees of inconsistency to finite sets of logical formulas. We first propose a basic set of postulates for consistency measures. We look at a couple of relationships with inconsistency measures. We even lay grounds for a formal duality between these two domains. Lastly, we have a look at what would be a mix measure, that is, a measure that gives a degree, on the same scale, for consistency (positive values) and inconsistency (negative values). We also mention supermodels, as defined by Ginsberg et al., as well as a theory that can be regarded as a generalization of super-models, namely morpho-logics.


Orateur : Hans van Ditmarsch (LORIA)
Titre : Dynamic epistemic logic for distributed computing – asynchrony and concurrency
Résumé : We will present some recent work on asynchrony and concurrency in dynamic epistemic logics (DEL), building on foundations in distributed computing and temporal epistemic logics. Asynchrony can be modelled by reasoning over histories of actions of different length. How to do this in DEL was proposed by [Dégremont, Löwe, Witzel: TARK 2011]. By equivalence relations on protocol-generated forests along different depths of trees, they can identify action histories of different length. More or less strongly related to DEL this was also considered for: gossip protocols [Apt, Grossi, vd Hoek, TARK 2015], logic puzzles [vD, van Eijck, Wu: KR 2010], and for the immediate snapshot algorithm in distributed computing [Goubault, Ledent, Rajsbaum: GandALF 2018]. We will present the last in some detail: Kripke models and action models can be represented as simplicial complexes. Dynamic epistemic logic can then be interpreted on such complexes. From the perspective of dynamic epistemic logic, a further departure towards distributed computing and asynchrony is to distinguish the sending and receiving of messages, such as the making versus hearing of announcements. Recent proposals are [Knight, Maubert, Schwarzentruber; MSCS 2019] and [Balbiani, vD, Fernandez Gonzalez; ArXiV 2019] (SR 2017). From the latter we will present asynchronous announcement logic. Its axiomatization resembles that of public announcement logic, and the dynamic modalities can also be eliminated. Further research is on (what is known as) concurrent common knowledge. Finally, how do we model concurrency in DEL? Both true concurrency and intersection concurrency are conceivable. We recall some older work in the area: [vD, vd Hoek, Kooi: AAMAS 2003] and [van Eijck, Sietsma, Wang: JANCL 2011]. The Muddy Children Problem is a joy forever: the action of three muddy children not stepping forward because none of them know whether they are muddy, is always modelled as the public announcement of a conjunction with three conjuncts. Should this not be a concurrent action with three components?

Septembre 2019 — Algorithmique et Structures Discrètes

« Distributed labeling schemes on metrically defined graphs » par S. Ratel (LIS)
« Fast Algorithms for Unit Disk Graphs » par G. Dias da Fonseca (LIS)
« Two open problems of Digital Geometry with convex lattice sets » par Y. Gérard (LIS)

Orateur : Sébastien Ratel (LIS)
Titre : Distributed labeling schemes on metrically defined graphs


Orateur : Guilherme Dias da Fonseca (MCF, LIS)
Titre : Fast Algorithms for Unit Disk Graphs
Résumé : Unit-disk graphs are graphs whose $n$ vertices correspond to unit disks in the plane and whose $m$ edges correspond to pairs of intersecting disks. \emph{Graph-based} algorithms receive as input solely the adjacency representation of the graph while geometric algorithms receive the coordinates of the disks. In this talk, we consider approximation algorithms to two classic hard optimization problems: maximum independent set and minimum dominating set. We are particularly interested in algorithms whose running times are close to linear in the input size, i.e. close to $O(n+m)$ for graph-based algorithms and close to $O(n)$ for geometric algorithms. We will discuss four different approaches to obtain such algorithms: greedy, local search, strip decomposition, and shifting coresets, comparing their performance for different problems and graph classes. This work is based on multiple papers co-written by the author with Celina M. H. de Figueiredo, Vinicius G. Pereira de Sá, Raphael Machado, Gautam K. Das, and Ramesh K. Jallu.


Orateur : Yan Gerard (PR, UCA)
Titre : Two open problems of Digital Geometry with convex lattice sets
Résumé : A lattice set of $Z^d$ is digital convex if its real convex hull does not contain any other integer point than the ones of S. Problem 1: recognition of digital polyhedra. A n-digital polyhedron is the intersection of the lattice $Z^d$ with a polyhedron of $R^d$ with at most $n$ faces. Given $n$ and a convex lattice set $S$, we want to determine whether $S$ is a $n$-digital polyhedron. In dimension $d=2$, with $n=3$, the question is to determine whether there exists a triangle $T$ whose intersection with the lattice is $S$. Whatever the value of $n$, it is a very natural question related to polyhedral separability but it is still undetermined whether it is decidable in the cases where $d>3$ and $S$ is hollow (hollow means that the interior of its convex hull does not contain any integer point). Problem 2: Discrete Tomography We consider the problem of reconstruction of convex lattice sets (or HV-convex polyominoes) from their horizontal and vertical X-rays or projections. In other words, we know the number of points of a convex lattice set $S$ on each row and column, and we want to reconver $S$. It’s not known whether it can be done in polynomial time. The usual approach to tackle the problem is based on some combinatorial objects called the switching components. We present some recent results abour their structures.

Juin 2019 — Géométrie et Topologie du Calcul

« Back to the Coordinated Attack Problem » par E. Godard (LIS)
« Analyse et reconstruction de modèles 3D » par A. Bac (LIS)
« Faster computation on simple topologies » par C. Maria (INRIA)

Orateur : Emmanuel Godard, LIS
Titre : Back to the Coordinated Attack Problem
Résumé : We consider the well known Coordinated Attack Problem, where two gener- als have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way mes- sages can be lost, i.e. we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simulta- neous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary con- dition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.
Joint work with Eloi Perdereau


Orateur : Alexandra Bac (MCF), LIS
Titre : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques

Résumé : Avec la généralisation de l’outil informatique dans tous les domaines de la société civile, la modélisaton géométrique est devenue une plaque tournante incontournable. Pour expliquer son essor, commençons peut-être par une tentative de définition :
« La modélisation géométrique, à la croisée des Mathématiques et de l’Informatique Graphique, a pour but de construire et analyser des modèles virtuels d’objets réels ou virtuels. »
Différents facteurs ont contribué à élargir le statut de la modélisation géométrique pour le faire passer de discipline relativement académique à celui d’outil applicatif indispensable :

  • d’une part, l’essor des modèles virtuels comme outils (la conception assistée par ordinateur est devenue un passage obligé dans tous les domaines de l’industrie et du design),
  • d’autre part, celui des méthodes de télédétection (que ce soit dans le médical, physique, chimie, génétique urbanisme, archéologie, géologie, aéronautique, étude de l’univers, de la terre, du sous-sol, des environnements naturels ou marins …),
  • enfin avec la confirmation de la loi de Moore, les capacités de traitement des ordinateurs ont atteint une développement suffisant pour permettre l’application d’algorithmes jusque-là inaccessibles sur les masses de données générées par les moyens de télédétection modernes.
    La topologie, quant à elle, étudiant “les propriétés invariantes sous l’effet de transformations biunivoques continues” (Riemann), est longtemps restée un domaine de recherche purement mathématique. Cependant, avec le développement de l’informatique et de la recherche informatique, cette frontière a rapidement fissuré, ouvrant le pas à l’étude algorithmique de la topologie des objets discrets. La topologie algébrique, branche de la topologie générale, vit ainsi naître son pendant numérique : la topologie algébrique algorithmique.
    La présentation abordera deux grandes pôles contiguës et complémentaires :
  1. la géométrie (principalement la géométrie des surfaces)
  2. la topologie algorithmique (et plus particulièrement l’homologie algorithmique)

Orateur : Clement Maria, INRIA
Titre : Faster computation on simple topologies
Résumé : The complexity of solving topological problems on surfaces often depends on the topology of the input surface. For example, deciding whether a graph can be embedded on a surface is NP-hard in general, but becomes only linear time on the size of the graph if the genus of the surface is considered constant. In this talk, we focus on a powerful topological invariant of 3-manifolds satisfying a similar property. Specifically, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariant at the fourth root of unity, using the dimension of the first homology group of the manifold as parameter. This invariant is #P-hard to compute in general. This is joint work with Jonathan Spreer.

Mars 2019 — Logique et Méthodes formelles

« Synthesizing robust controllers for Büchi conditions in timed systems » par D. Busatto-Gaston (LIS)
« Programmation logique au sens ASP » par B. Benhamou (LIS)
« Assume Admissible Synthesis » par J.F. Raskin (ULB)

Orateur : Damien Busatto-Gaston (PhD) , LIS
Titre : Synthesizing robust controllers for Büchi conditions in timed systems.
Résumé : We solve the robust controller synthesis problem in timed automata with Büchi acceptance conditions. The goal of the controller is to play according to an accepting lasso of the automaton, while resisting to timing perturbations chosen by a competing environment. The talk will introduce classical notions for studying timed automata (regions, zones, constraint graphs) and explain how these can be extended to compute strategies that are resilient to arbitrarily small perturbations. We will also introduce a way to compute the largest perturbation allowed by a given controller. Our techniques are illustrated by the regulation of a train network.


Orateur : Belaid Benhamou (MCF), LIS
Titre : Programmation logique au sens ASP (Answer Set Programming) : une nouvelle sémantique capturant et étendant celle des modèles stables.

Résumé : Plusieurs travaux ont été faits pour définir des sémantiques pour les programmes logiques normaux. La plupart de ces sémantiques sont en fait des sémantiques de points fixes. L’idée principale est le calcul de modèles canoniques du programme logique considéré, appelés modèles stables (Gelfond et al. 1988).

Dans cette exposé, nous décrivons une nouvelle sémantique pour les programmes logiques normaux. Cette dernière est basée sur une notion d’extensions de formules propositionnelles classiques. Un programme logique est alors codé par un ensemble de clauses de Horn propositionnelles. On prouve que chaque formule consistante (ou programme logique) admet au moins une extension et que, pour chaque modèle stable d’un programme logique, il existe une extension de son codage logique qui l’implique. Certaines extensions (extra-extensions) ne correspondent pas à des modèles stables du programme logique, mais sont intéressantes car elles représentent ici, une extension pour la sémantique des modèles stables. Nous donnons une condition discriminante simple qui permet de reconnaître les extensions « normales » et les distinguer des extra-extensions.

Basé sur cette sémantique, nous proposons une nouvelle méthode de recherche de modèles stables pour les programmes logiques. Elle a l’avantage d’utiliser un ensemble de clauses de Horn et travaille à espace constant. Elle évite ainsi, la lourdeur induite par la gestion des boucles, dont souffrent la plupart des solveurs ASP utilisant la complétion de Clark et qui ont des complexités spatiales exponentielles dans le pire des cas. De plus, l’énumération est effectuée sur un ensemble restreint de variables du programme logique. Ce qui réduit en général, la complexité temporelle de l’algorithme. En plus de la recherche de modèles stables, cette méthode pourrait générer une sorte d’extra-modèles stables exprimant ainsi l’extension portée à la sémantique des modèles stables.


Orateur : Raskin Jean-Francois, ULB
Titre : Assume Admissible Synthesis.
Résumé : In this talk, I will show how the notion of admissibility can be used to provide an elegant solution to the synthesis problem for reactive system where the environment is not completely adversarial or when the system is composed of several components. In particular, I will introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. Contrary to previous proposals in the literature, the rule « assume admissible » defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each component.