**Présentation:**

- Le séminaire est organisé par le LORIA

(CNRS – Inria Nancy G. E.- Université de Lorraine) - Il se tient (sensiblement) deux fois par mois
- Il cherche à fomenter les échanges entre les chercheurs français et étrangers par la présentation de leurs travaux récents
- Les manifestations des jeunes chercheurs sont bienvenues
- Il est animé par l’équipe Orpailleur : Miguel Couceiro, Amedeo Napoli
- Les thèmes abordés sont très variés et portent sur les sciences de l’information et de la vie: mathématiques discrètes (théorie des graphes, des ensembles ordonnés, algèbre, combinatoire), mathématiques de la décision et de l’information (théorie de l’agrégation, théorie du choix social, aide à la décision, théorie des jeux), logique (modélisation, représentation et raisonnement sur des connaissances) et intelligence artificielle (apprentissage artificielle, analyse de donnés, data mining, optimisation combinatoire),…

**Programme:**

- Mercredi, le 5 octobre 2016, de 15h à 16h, Salle: B013 (LORIA):
François Pirot:

*The bounds for the distance-t chromatic number, and the effect of removing cycles*

**Résumé :**It is well known that you can colour a graph G of maximum degree*d*greedily with*d+1*colors. Moreover, this bound is tight, since it is reached for example by the cliques. Johansson proved with a pseudo-random colouring scheme that you can colour triangle-free graphs of maximum degree*d*with no more than O(*d/log d*) colours. This is tight up to a multiplicative constant, since you can pseudo-randomly construct a family of graphs of maximum degree*d*, arbitrary large girth, and chromatic number bigger than*c*(*d/log d)*, for some constant*c*.

When you introduce the distance-t chromatic number of a graph*G*of maximum degree*d*, which is simply the chromatic number of*G^t*, you can be interested in finding similar bounds, and proving that they are tight. It is straight-forward that*d^t*is an upper bound for the distance-t chromatic number, but determining how tight this bound is is far from being an easy problem. You may also wonder what happens to the bound of the distance-t chromatic number when you forbid some fixed lengths of cycles in your graph. The goal of my talk will be to give some answers to these natural questions. - Vendredi, le 3 juin 2016, de 11h à 12h00, Salle: B013 (LORIA):

Pauli Miettinen: *Matrix factorization models for patterns beyond blocks
*

**Résumé :**Finding patterns, or regularities, from data and using the patterns to summarise the data are in the core of data mining. In many cases, these pattens are « block-like »: when the data can be expressed as a table of values, or as a matrix, the patterns are sub-tables (or sub-matrices) that are somehow different from the other parts of the data. Clustering, community detection, and frequent itemset mining can all be considered to find « block-like » patterns, to name a few examples. Block-like patters also fit well to the language of linear algebra, where we can model the block-like patterns as (approximate) rank-1 matrices, and data summarisations as matrix factorisations. Not all patterns or summaries in data mining are easy to express as matrix factorisations, though, and in recent years, patterns that go « beyond blocks » have become under active investigation. In this talk, I will discuss why being able to express the data mining task in matrix factorisation terms is important and cover my recent and ongoing work on different types of matrix factorisations that can be used to model patterns beyond blocks.

- Mercredi, le 18 mai 2016, de 14h à 15h00, Salle: B013 (LORIA):

Gerasimos Meletiou: *Secret Sharing Through Multivariate Birkhoff’s Interpolation
*

**Résumé :**The problem of finding secret sharing schemes with multilevel structures and partially ordered sets of levels of participants is faced. We investigate the idea of generalizing previous schemes (Shamir’s, Tassa’s) through multivariate Birkhoff’s interpolation.

- Jeudi, le 12 mai 2016, de 11h à 12h00, Salle: B013 (LORIA):

Sergei O. Kuznetsov: *Optimizing Therapy in Subgroups of Patients with Pattern Structures
*

**Résumé :**The effectiveness of a therapy of serious lethal diseases is measured by survival curves. A therapy is better than another one if its survival curve lies strictly above. For standard randomisation strategies accepted in medical science, two therapies may be of same quality, however if we consider subgroups of patients defined by common physiological features, one treatment can be strictly better than another for certain subgroups. Closed descriptions is a very natural way for concise representation of subgroups, so we describe an efficient approach for finding closed descriptions of groups where some treatments are definitely preferred to others. The approach can be applied in other domains like optimal credit scoring.

**Symposium Mathematics for Decision and Discovery (M4D2)**

**Mercredi, 11** **mai 2016** (B013, LORIA): Program

- Vendredi, le 15 avril 2016, de 14h à 15h00, Salle: B013 (LORIA):

Benjamin Momège: *Autour de la connexité dans les graphes avec conflits
*

**Résumé :**Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

- Vendredi, le 15 avril 2016, de 11h à 12h00, Salle: B013 (LORIA):

Bruno Teheux: *Automates, mots et décision
*

**Résumé :**Fonctions qui transforment les mots, automates, problèmes de décisions… Dans ce séminaire, nous mettrons en évidence des liens entre ces différents ingrédients avec une équation très connue comme pivot: l’équation d’associativité.

- Mardi, le 9 février 2016, de 11h30 à 12h30, Salle: B013 (LORIA):

Lucien Haddad: *Partial clones and the Erdös-Faber-Lovsáz conjecture
*

**Résumé :**Let A be a finite set. A partial clone on A is a set of partial functions closed under composition and containing all projection functions on A. We survey some results in the theory of partial clones. In particular: (1) we show the link between The Erdös-Faber-Lovsáz conjecture for graphs and combinatorial descriptions of some maximal partial clones, and (2) we give a complete classification of certain intervals of partial clones, that solves an open problem by D. Lau. These results were obtained in collaboration with (1) C. Tardif and (2) M. Couceiro, K. Schölzel and T. Waldhauser.

- Lundi, le 7 décembre 2015, de 11h30 à 12h30, Salle: B011 (LORIA):

Fabien Labernia: *Conditional preferences network : an overview
*

**Résumé :**Let V be a set of binary variables. Elicitating preferences over the set of all possible assignments for V to obtain a partial (or total) order can be a very long and difficult task. Different models have been proposed to 1) help the expert to elicit these preferences (ceteris paribus preferences), 2) represent in a compact way this exponential set (conditional preference rules) and 3) catch in a formal way some preference properties (such as importance of a variable). In this presentation we will survey different models like CP-nets, TCP-nets, CP-theories and CI-nets (the different properties they catch, active learning of these models), and discuss some current research directions on these combinatorial structures.

- Mardi, le 1 décembre 2015, de 11h à 12h00, Salle: B013 (LORIA):

Bruno Teheux: *A modal logic for games with lies
*

**Résumé :**In the Rényi-Ulam game, a liar picks out a number in a given search space. A second player has to guess this number by asking Yes/No questions to the liar who is allowed to lie a maximal given number of times. It is known that states of the game can be encoded in the algebraic language using MV-algebras (which are to Łukasiewicz logic what Boolean algebras are to classical propositional logic). The aim of the talk is to present an (n+1)-valued version of Propositional Dynamic Logic (PDL) that is suitable to model the interactions between players in the Rényi-Ulam game. The ingredients of this model are modal expansions of Łukasiewicz finitely-valued logics, algebras of regular programs and many-valued Kripke models. Our main result will be a completeness result. We will also discuss the gain of expressive power allowed by the new many-valued dynamic language.

- Mardi, le 24 novembre 2015, de 13h à 14h00, Salle: B013 (LORIA):

Kevin Dalleau: *Suggesting valid pharmacogenes by mining linked data
*

**Résumé :**A standard task in pharmacogenomics research is identifying genes that may be involved in drug response variability, i.e., pharmacogenes. Because genomic experiments tended to generate many false positives, computational approaches based on the use of background knowledge have been proposed. Until now, those have used only molecular networks or the biomedical literature. Here we propose a novel method that consumes an eclectic set of linked data sources to help validating uncertain drug–gene relationships. One of the advantages relies on that linked data are implemented in a standard framework that facilitates the joint use of various sources, making easy the consideration of features of various origins. Consequently, we propose an initial selection of linked data sources relevant to pharmacogenomics. We formatted these data to train a random forest algorithm, producing a model that enables classifying drug–gene pairs as related or not, thus confirming the validity of candidate pharmacogenes. Our model achieves the performance of F-measure=0.92, on a 100 folds cross-validation. A list of top candidates is provided and their obtention is discussed.

**Symposium on instant data mining and learning preferences for interactive data mining**(PEPS Préfute + Approppre)

**Jeudi, 19** **Novembre 2015** (C005, LORIA): Program

**Vendredi, 20 Novembre 2015** (B013, LORIA):

Victor Codocedo: *When Cyberathletes Conceal Their Game: Clustering Confusion Matrices to Identify Avatar Aliases*

- Jeudi, le 1 octobre 2015, de 11h à 12h00, Salle: B013 (LORIA):

Renato Vimieiro: * Mining disjunctive emerging patterns in high-dimensional data using hypergraphs
*

**Résumé :**Pattern mining is one of the most known sub-fields of data mining. Its main goal, as originally proposed by Agrawal et al., is to identify sets of attributes that are frequent amongst objects in a dataset. Most of the applications of (frequent) pattern mining involve the analysis of market basket data. In this type of data the attributes are binary and the data table is a matrix where objects are rows, attributes columns and cells indicate whether an object has an attribute. Since the beginning, the area has been extensively investigated and a wealth of efficient algorithms proposed. Although the original proposition was very successful in many domains, it was not suitable for the analysis of labelled data, i.e., data where objects had class labels. Thus one extension to frequent pattern mining, to cope with this type of data, was proposed in 1999 by Dong and Li. Their idea, named

*emerging patterns*, was to extract patterns that were frequent amongst objects with one class label and infrequent amongst the others. Emerging patterns showed to be effective in many applications involving labelled data, particularly those in bioinformatics. In this presentation a new extension to emerging patterns will be briefly discussed. An overview of disjunctive emerging patterns will be given and an efficient algorithm based on hypergraphs and their minimal transversals for mining these patterns will be introduced.

- Lundi, le 30 juin 2015, de 12h00 à 13h00, Salle B013 (LORIA):

**12h00 – 12h30** Kenny Rivalin: *Systèmes de recommandation dans le cadre de l’analyse de concepts formels*

**12h30 – 13h00 **Benjamin Maurice: *Extraction de cliques et de quasi-cliques maximales sur des graphes creux*

- Mardi, le 29 juin 2015, de 11h00 à 12h00, Salle C005 (LORIA):
Maurice Pouzet:

*Boolean dimension of a graph and inversion index of a tournament*

**Résumé :**The*Boolean dimension of a graph G*(undirected with no loops) is the least integer*m*for which there exist*m*subsets X1, … , X*m*of the vertex set V(*G*) of*G*such that the edges of*G*are exactly the 2-element subsets*e*of V(*G*) which are included into an odd number of the X*i*‘s. If*G*has*n*vertices, its Boolean dimension is at most*n-1*; it is*n-1*if and only if*G*is a path. The inversion of a subset X of the vertex set V(*T*) of a tournament*T*consists to invert all arcs of*T*between two vertices of X. The*inversion index*of*T*is the least number, denoted by*i*(*T*), of subsets of V(*T*) to invert in order to transform*T*into an acyclic tournament. I will present the main results and two tantalizing problems: the value of the inversion index of paths of strong connectivity, a majoration of the size of obstructions of the class I(*n*) of finite tournaments whose inversion index is a most*n*(the fact that there is a bound follows from techniques of well quasi ordering). Results presented here originate in the thesis of H. Belkhechine [1]. They have been obtained in collaboration with H. Belkhechine, M. Bouaziz and I.Boudabbous and announced in [2].

[1] H. Belkhechine, Indécomposabilité des graphes et des tournois, thèse de doctorat, 15 juillet 2009, Université Claude-Bernard et Université de Sfax.

[2] H. Belkhechine, M. Bouaziz, I. Boudabbous, M. Pouzet, Inversion dans les tournois, C. R. Acad. Sci. Paris, Ser. I 348 (2010) 703-707. - Vendredi, le 5 juin 2015, de 11h00 à 12h00, Salle B013 (LORIA):
Abdallah Saffidine:

*Solving Games and all of that*

**Résumé :**Efficient best-first search algorithms have been developed for deterministic two-player games with two outcomes. We present a formal framework to represent such best-first search algorithms. The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm. We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K. This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions. We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves. - Jeudi, le 4 juin 2015, de 11h00 à 12h00, Salle A117 (LORIA):
**11h00 – 11h30 :**Justine Reynaud*Définition d’un langage de transformation de requêtes SPARQL*

**11h30 – 12h00 :**Quentin Brabant*Axiomatisation des intégrales de Sugeno k-maxitives* - Mardi, le 5 mai 2015, de 14h00 à 15h00, Salle B011 (LORIA):

Erkko Lehtonen: *Homomorphisms of labeled posets*

**Résumé : **A *partially ordered set labeled with k labels* (a

*) is a triple (*

*k*-poset*P*, ≤,

*c*), where (

*P*, ≤) is a partially ordered set and

*c*:

*P*→ {0, …,

*k*− 1} is a labeling function. A

*homomorphism*of a

*k*-poset (

*P*, ≤,

*c*) to another

*k*-poset (

*P′*, ≤′,

*c′*) is a map

*h*:

*P*→

*P′*that preserves both the order and the labels, i.e.,

*h*(

*x*) ≤′

*h*(

*y*) whenever

*x*≤

*y*and

*c*=

*c′*⚬

*h*. The set of all

*k*-posets is partially ordered by the existence of homomorphism. We present some results concerning the structure of this homomorphism order. In particular, for

*k*≥ 2, the homomorphism order of finite

*k*-posets is a distributive lattice that is universal for countable posets. We also discuss the complexity of certain decision problems involving labeled posets. This talk is partly based on joint work with Léonard Kwuida.

- Mardi, le 28 avril 2015, de 12h00 à 13h00, Salle B013 (LORIA):

Michel Grabisch: *Games on concept lattices*

**Résumé : **We introduce cooperative TU-games on concept lattices, where a concept is a pair (S,S’) with S being a subset of players or objects, and S’ a subset of attributes. Any such game induces a game on the set of players/objects, which appears to be a TU-game whose collection of feasible coalitions is a lattice closed under intersection, and a game on the set of attributes. We investigate the geometrical properties of the core (non-emptiness, boundedness, pointedness, extremal rays). In particular, we derive the equivalence of the intent and extent core for the class of distributive concepts.