14/05/2024 – Yi ZHOU : Recent advances in algorithms for k-plex problems
In the field of graph mining, the k-plex is a well-known extension of the basic clique model. A k-plex is nearly a clique except that each vertex is allowed to be not adjacent to at most k vertices, with k being a positive integer. When k=1, a k-plex is equivalent to a clique. Fundamental problems related to the k-plex include how to enumerate all maximal k-plexes and how to find the maximum k-plexes in a given graph. In this talk, I will present some of our recent results on these problems from the perspective of algorithm engineering. I will also introduce how techniques in the design of exact and parameterized algorithms assist in the analysis of practical k-plex algorithms.
24-26/01/2024 – Seed workshop
25/09/2023 – Matinée Musique & IA
Lien vers le programme, les présentations et les photos de l’événement
24/05/2023 – Vorapong Suppakitpaisarn : On the maximum edge-pair embedding bipartite matching
Given a set of edge pairs in a complete bipartite graph, we want to find a bipartite matching that includes the maximum number of those edge pairs. While the problem has many applications to wireless localization and computer vision, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless P = NP, we show that there is no constant approximation for the problem. Then, we consider two special cases of the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, the first case is for when k is not large. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O(k)-approximation algorithm for the problem. For the second case, every pair of nodes in the same partition of the input bipartite graph are labeled with one of χ colors. We want to match, between the two partitions, a pair of nodes to a pair of nodes with the same color. Denote n as the number of nodes, we give an O (√χn)-approximation algorithm for this case
17/04/2023 – Benoît Delahaye : Modélisation et vérification statistique pour les systèmes Naturels
La modélisation et l’analyse de modèles sont centrales dans toutes les disciplines scientifiques, mais les formalismes et techniques formelles développées en Informatique théorique sont souvent peu adaptées aux problématiques des sciences “naturelles”. La paramétrisation et l’analyse de stabilité de modèle différentiels sont des questions pratiques, issues de problématiques réelles dans le cadre des systèmes naturels, que les méthodes formelles informatiques peinent à appréhender. Dans cet exposé, je présenterai comment la vérification de modèles statistique peut être combinée à des méthodes d’intégration numérique pour proposer des réponses à ces questions dans un cadre générique tout en préservant des garanties formelles.
08/03/2023 – Malak Belkebir : Proposal of semantic models for the improvement of standard image processing methods based on inductive inference.
Nowadays, imaging and artificial vision have become important fields of research due to their underneath applications. These last have reached a high level of usefulness thanks to the used techniques. For instance, deep learning, a well-known technique, has proven its capabilities in terms of theoretical and research-level results as well as practical applications. Nevertheless, despite the high accuracy that has been achieved by their techniques, most of them remain “quantitative approaches”,i.e. “data-driven approaches”; their efficiency depends on the computational capacity and requires a large amount of data for training and testing. Furthermore, there are still many deficiencies, such as the semantic gap between the low-level visual information and high-level semantic knowledge, the recognition of complex scenes and so on. With the aim of providing less costly and more efficient solutions, the new trend is to make it possible for the aforementioned fields to support knowledge representation techniques i.e. “qualitative- approaches”, which is at first sight ontological. This presentation provides an overview of various research studies that have demonstrated the effectiveness of this combination, including formal methods, first-order logic, deep learning, and imaging. Additionally, it includes a contribution to this field, along with some results and a case study.
02/03/2023 – Javier Yuste : Automatic improvement of software quality: optimization strategies for software maintainability.
Search-Based Software Engineering is a research area that aims to tackle software engineering tasks as optimization problems. Among the problems in this area, we can find the Software Module Clustering Problem (SMCP), which has been proved to be NP-hard. This problem focuses on finding the best organization of a software project in terms of modularity. Since modular code is easier to understand, the objective of this problem is to increase the quality of software projects and thus reduce the costs associated to their maintenance. To tackle the SMCP, software projects are often modeled as graphs, representing the dependencies between different components of the code. To cluster the resulting graphs, we present two different algorithms based on the Greedy Randomized Adaptive Search Procedure and the Variable Neighborhood Search frameworks. Furthermore, we introduce some advanced strategies that enhance the efficiency of the proposed algorithms, accelerating the computation of the objective function and avoiding the exploration of unpromising solutions in the search space. Finally, we compare the proposed methods over a set of 124 real software projects, studying two objective functions: Modularization Quality (MQ) and the Function of Complexity Balance (FCB). The obtained results show that the proposed algorithms obtain better results than the previous state-of-the-art proposals. Moreover, the difference in the results is shown to be statistically significant with a p-value lower than 0.01, according to non-parametric statistical tests.
10/01/2023 – Véronique Ventos : Nook : a new generation AI dedicated to the game of Bridge.
Plusieurs défis se posent aujourd’hui à l’Intelligence Artificielle 1/ véritable collaboration entre l’humain et la machine 2/ transparence et confiance dans les décisions 3/ sobriété énergétique. Pour répondre à ces défis, le laboratoire de recherche privé NukkAI a utilisé comme bac à sable le jeu de Bridge qui résiste encore à l’IA le niveau des robots existants étant très loin de celui des meilleurs joueurs humains. Lors d’un challenge organisé les 25 et 26 Mars 2022 à Paris, l’IA de bridge Nook a battu 8 champions du monde de bridge. Au-delà de cette première mondiale, Nook permet de montrer l’avantage de ne pas rester dans un cadre mono paradigme même si celui-ci est très à la mode. En effet, notre robot est une IA hybride dont les modules proviennent de différents paradigmes interagissant entre eux. Dans cette présentation, nous commencerons par brièvement décrire NukkAI et ce que nous entendons par IA nouvelle génération. La seconde partie sera consacrée aux notions de base du bridge et à la description du challenge. Enfin, nous présenterons les différents modules de recherche de Nook.
08/12/2022 – François Olivier
The ASPMT tool generalizes the “Answer Set Programming” approach to allow reasoning Modulo a certain underlying Theory. The presentation will focus on the use of ASPMT with non-linear arithmetic constraints, as well as on the possible applications offered by this system, such as the modelling of human spatial reasoning in cognitive sciences.
27/10/2022 – Sylvain Lamprier : Apprentissage Statistique et Inférence Bayésienne pour Données Séquentielles et Relationnelles.
26/08/2022 – Tomasz Jastrzab : Parallel constraint solving
During the talk, selected parallel computing models will be shown along with their implementations. The constraint solving part of the talk will focus on solving the problem of nondeterministic automata inference using SAT-based models and solvers. The advantages and problems related to using parallel computing will be discussed.