25 of June, 2024
Description: The main goal of M4D2 is to bring together researchers from fields of computer science that may seem at first glance rather distant but that share in fact several common points. This will be the third event of the M4D2 series!
This M4D2 is organized by M. Couceiro and P. Monnin in the framework of the MALOTEC seminar (the French acronym for « Seminar of mathematics and logic for knowledge discovery ») held in the ORPAILLEUR Team, at LORIA.
The main topics of the 3rd symposium M4D2 will be
I. Universal algebra and combinatorics
II. Analogy reasoning and Large language models
All members of LORIA, IECL, CRAN and other computer science and mathematics laboratories, are most welcome!
Localization: A008, LORIA
Program:
9h00-9h45: Victor Langerkvist (Linköping University)
Title: Fine-grained complexity of constraint satisfaction problems
Abstract: The constraint satisfaction problem (CSP) is a widely studied combinatorial problem with fundamental applications in AI. The problem is in general NP-hard but admit many non-trivial tractable subproblems, and for constraints over finite domains a complete separation of tractable and NP-hard subproblems has been established, the so-called CSP dichotomy theorem. During this seminar we will briefly survey some techniques crucial for obtaining this theorem, and explain how they can be modified and extended to study slightly more nuanced complexity questions pertaining to NP-hard CSPs.
10h00-10h45: Jovanka Pantovi\’c (University of Novi Sad)
Title: From Completeness of Operations to Completeness of Relations: My Journey
Abstract: The completeness property is essential in ensuring that algebraic, logical, or computational systems accurately represent complex systems they are designed to model. When considering algebraic systems, a complete set of operations refers to the set of operations that is sufficient to generate any operation within that system. My research journey began by exploring the complete sets of operations on a finite set, containing some given fixed elements, and counting the numbers of closed sets which they generate. It has since branched out in several directions, one of which is to consider type systems for providing security and privacy in concurrent and distributed computing systems.
In this talk, I will focus on more recent results that consider the soundness and completeness of a subtyping elation for multiparty session types. In computing systems that consist of distributed components running concurrently, interactions are usually performed via message-passing, respecting some predefined communication protocols. One of the main concerns in this field is to ensure that components of such a system respect the given protocol, while avoiding communication errors and deadlocks. Multiparty session types presents a concept that was developed to formally model communication protocols and ensure absence of undesired behaviors. In this framework, we are interested in development of precise subtyping relations, meaning that they are both sound and complete. Not only that we know that a process implementing a multiparty session type T is safe in places where a process of type T’ expected, when T is a subtype of T’, but we also know that such a relation is maximal. If T is not a subtype of T’, we are sure that similar replacements can cause undesired failures.
11h00-11h45: Pierre Charbit (Université Paris Cité, IRIF)
Title: Chromatic Number and Clique Number for Tournaments.
Abstract: The chromatic number and clique number are well-studied notions that have motivated a significant part of the research in graph theory in the last century. However, analogue notions long lacked in the directed case. In 1982, Victor Neumann-Lara proposed a definition for colouring directed graphs, which proved to be fruitful, especially since its reintroduction by Mohar in 2003. However, a notion of clique number for directed graphs was missing. In this presentation, we will explore a definition we found relevant, and the first results we found, mimicking existing results on undirected graphs.
This presentation will mainly focus on a joint work with Pierre Aboulker, Guillaume Aubian and Raul Lopes.
12h00-14h00: Lunch
14h00-14h45: Dafna Shahaf (Hebrew University of Jerusalem)
Title: TBA
Abstract: TBA
15h00-15h45: Zied Bouraoui (Université d’Artois, CRIL)
Title: Reasoning with Propositional Logic Assertions Using Transformers-Based Langage Models.
Abstract: Natural language provides an appealing alternative to formal logics for representing knowledge. However, using natural language prevents the application of standard automated reasoning methods. A common solution involves employing transformer-based language models to reason directly with knowledge expressed in natural language. This approach has two significant limitations. First, the set of premises is often too extensive to be directly processed by the LM, necessitating a retrieval strategy to select the most relevant premises for inference. Second, LMs tend to learn shortcuts, lacking robustness and raising doubts about their true understanding of the expressed knowledge. In this talk, I will present an alternative approach to overcome these limitations by learning embeddings of propositional logic formulas in which reasoning is then carried out.
16h00-16h45: Miguel Couceiro (University Lorraine, LORIA & IST, Universidade de Lisboa, INESC-ID)
Title: Unifying numerical analogies
Abstract: In this talk we will present a framework for modeling analogies that we recently proposed with Yves Lepage. This framework exploits tight relationships between analogies and generalized means, and unifies different models of numerical analogies.
We will discuss pertaining questions such as invariance properties, the semantics and the expressive power of such analogies. Wewill also explore further topics related to equivalence classes and invariance properties, generalized mean approximations, manifold representations, as well as algorithmic aspects and machine learning applications such as machine classification.
17h00-18h00: « Farewell reception »