Séminaire MAGMAT, Vendredi 17 Avril

Ce vendredi à 10h30 en salle 301 nous accueillons Florent Madelaine (Université de Caen/Université de Clermont-Ferrand).

The complexity of QCSP :  when is it in NP?

The Quantified Constraint Satisfaction Problem (QCSP) allows to model uncertainty or lack of control of some variables. This extension of the classical setting of Constraint Satisfaction comes at a price : the problem is Pspace-complete rather than NP-complete. An ongoing program aims at classifying the complexity of the QCSP for each constraint language, and known results suggest that the QCSP could follow a trichotomy between Pspace-complete, NP-complete and tractability (in Ptime). However, most complexity results for the QCSP are of the form NP-hard vs tractable. While these results are important and interesting, we wish to better understand the Pspace-complete vs NP question in QCSPs.

Collapsibility is a natural property of a constraint language introduced by Hubie Chen, which implies a drop in complexity of the associated QCSP from Pspace-complete to NP. This property covers all known natural example of constraint languages with a QCSP in NP.

In this talk, I will present some new results on collapsibility. Our main result is that we can decide in several natural cases whether a constraint language is collapsible. This relies heavily on the fact that we can relate collapsibility for QCSP with collapsibility for the Pi2-restrictions of QCSP (when the values of universal variables are all known before existential variables). If times allows I will also explain how this result motivates further a purely algebraic gap question on size of generating sets for the sequence of powers of an algebra (polynomial vs exponential).

 Imprimer  E-mail

Séminaire ADAM, Jeudi 16 Avril

Vania Vidal, Professeur à l'Université Fédérale de Ceara à Fortaleza au Brésil, actuellement en visite au PRiSM, fera un séminaire ce jeudi 16/4 à 15h en salle 301 sur l'enrichissement sémantique de données de mobilité (voir description ci-dessous).

A Framework for Semantic Enrichment of Mobility Data with Linked Data

Recently, we have witnessed a growing research area where the representation of movement is not limited to raw trajectory, but is enriched with semantic information, resulting in the so-called semantic trajectories. The process of adding knowledge to raw trajectories is known as semantic enrichment. However, we still miss a comprehensive framework to organize this process and accommodate the different approaches in a single vision.

In my talk, I will present a conceptual framework for the semantic enrichment process of movement data based on Linked Data. The framework is structured into two levels, where the user transforms raw trajectories into semantic trajectories, at the first level, and performs additional analyses on the set of semantic trajectories, at the second level. We argue that the process of semantically enriching a trajectory at the first level can be viewed as a problem of interlinking the components of a trajectory with a Linked Data Mashup view.

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 03 Avril

Ce vendredi à 10h30 en salle 301 nous accueillons Nicolas de Rugy-Alherre (Paris 7).

Exposé d'introduction à la logique de dépendance.


La logique de dépendance et ses variantes (indépendance et inclusion) ont été introduites par Vänäänen il y a quelques années pour parler de façon "propre" de dépendance en logique. Je présenterai cette logique et ses résultats principaux en complexité.

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 20 Mars

Ce vendredi, nous aurons un séminaire à 10h30 en salle 301.
Arnaud Mary (Université de Lyon) viendra nous faire un exposé intitulé:

Dualisation multi-objectifs et applications en biologie.


Un hypergraphe $H$ est un couple formé d'un ensemble de sommets $V$ et d'une famille de sous-ensembles de $V$ appelés les hyperarêtes de $H$. Un transversal d'un hypergraphe est un sous-ensemble de sommets qui intersecte toutes les hyperarêtes de l'hypergraphe. Étant donnés deux hypergraphes $H_1$ et $H_2$ sur un même ensemble de sommets $V$, le problème de dualisation multi-obectif consiste à trouver tous les transversaux de $H_1$ qui intersectent un ensemble minimal d'hyperarêtes de $H_2$. Ce problème trouve plusieurs applications en biologie notamment dans la recherche de facteurs de transcription impliqués dans la mauvaise régulation de gènes au sein d'une tumeur.

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 6 Mars

Ce vendredi, nous aurons un séminaire à 10h30 en salle 301.
Joseph Salmon (Télécom Paris) viendra nous faire un exposé intitulé:

Mind the (duality) gap: safer rules for the Lasso.

The Lasso is an l1-regularization technique for least-square, having the nice property of inducing sparse solutions. Recently, screening variables has been considered to speed up optimization algorithms solving a Lasso problem or its derivatives.  We propose new versions of the so called safe rules for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero for any solver outputting a converging sequence toward a Lasso solution. This helps screening out more variables for a wider range of tuning parameters. In addition to faster convergence to a solution, we prove that we correctly identify active sets (supports) in finite time. Though our framework can encompass any solver, we have implemented our strategies on a popular coordinate descent version. We achieved noticeable computing time reduction with respect to former safe rules.

 Imprimer  E-mail

DMC Firewall is a Joomla Security extension!