Courcelle’s theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP-hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula.
In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle’s theorem is « best possible ». Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth.
Results based on a preprint found here: https://arxiv.org/abs/2210.09899
Tag : Français
Énumérer des objets est une tâche courante en informatique, que ça soit pour les compter, trouver une solution optimale ou constituer une librairie d’objets intéressants. Pour mesurer la complexité d’un algorithme d’énumération, on borne généralement le délai qui mesure le temps entre la production de deux solutions. Une mesure plus souple est le temps incrémental qui mesure le temps nécessaire à la génération de k solutions.
Il est fréquent de régulariser un processus à temps incrémental linéaire en utilisant un grand buffer pour stocker les solutions et les produire régulièrement afin d’obtenir un algorithme à délai polynomial. Malheureusement cette technique utilise un espace potentiellement exponentiel.
Nous allons présenter une méthode alternative, l’amortissement géométrique qui permet de régulariser un algorithme en espace polynomial et sans surcoût en temps. Nous montrerons que cette méthode fonctionne même quand on ignore l’espace utilisé et le nombre de solutions générées par l’algorithme qu’on régularise. Cette méthode est optimale, au sens ou nous donnons des bornes inférieures qui montre qu’il est impossible de faire de l’amortissement quand on ne connaît pas le délai ou qu’on veut respecter l’ordre des solutions.
En octobre 2022, la Ministre de l’Enseignement Supérieur et de la Recherche, Sylvie Retailleau, a annoncé que tous les étudiants suivront des enseignements spécifiques à la transition écologique au plus tard en 2025.
Après avoir rappelé le contexte et la pression grandissante sur l’enseignement supérieur pour former les étudiants à la transition écologique, je présenterai le cours « transition écologique » que j’ai enseigné au premier semestre aux étudiants de L1 Math/Info.
Je détaillerai le plan de ce cours généraliste: climat, énergie, réchauffement climatique, neutralité carbone, lien avec la biodiversité. Je donnerai des exemples d’activités/exercices proposés et préciserai l’évaluation.
Je ferai un retour d’expérience sur le déroulement du cours, ébaucherai les perspectives d’amélioration et de déploiement envisageables et évoquerai les difficultés potentielles de mise en oeuvre d’un tel cours à une plus grande échelle.
Enfin, je terminerai en élargissant la problématique de la transition écologique au laboratoire.
A geometric transversal to a family of convex sets in the d-dimensional Euclidean space is an affine flat that intersects the members of the family. While there is a well-developed theory concerning 0-dimensional transversals (« intersection patterns of convex sets’’) with deep connections to algebraic, enumerative, geometric, and topological combinatorics, much less is known when it comes to higher-dimensional transversals. In this talk, I will give an introduction to this field of study and highlight some new and old results and open problems. This is based in part on joint work with Otfried Cheong and Xavier Goaoc.
We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $mos(G)$ and $\Chi_{odd}(G)$, respectively. We prove that deciding whether $\Chi_ {odd} (G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise.
We provide algorithms in time $2^{O(rw)} \cdot n^{O(1)}$ and $2^{O(q \cdot rw)} \cdot n^{O(1)}$ to compute $mos(G)$ and to decide whether $\Chi_ {odd}(G) \leq q$ on $n$-vertex graphs of rank-width at most $rw$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
Joint work with Ignasi Sau.
RNA molecules consist of chains of individual blocks called nucleotides (A, U, G, C), and perform a wide variety of functions in biological systems. These functions critically depend on the 3D structures adopted by these molecules, i.e., the way nucleotides are paired up in complex folding conformations.
Several natural computational problems involving this structure then emerge, such as folding (what is the preferred structure of an RNA sequence?) or structure reconfiguration (is there a feasible reconfiguration path between these two structures?). These problems are typically computationally hard, especially when going towards realistic biological models.
This talk will focus on selected instances of such landmark problems, and on current attempts to tackle them with exact parameterized algorithmics. A particular focus will be given to graph algorithms, and graph width parameters. Examples of graph problems emerging from this angle include minimum edge deletion towards a target treewidth value [1], or the computation of directed pathwidth for a particular geometric subset of directed graphs [2].
References:
[1] B. Marchand, Y. Ponty, L. Bulteau. Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics. Algorithms for Molecular Biology 2022.
[2] L. Bulteau, B. Marchand, Y. Ponty. A new parameterization for independent set reconfiguration and applications to RNA kinetics. IPEC 2021.
Runtime verification consists in checking whether a program satisfies a given specification by observing the trace it produces during its execution. In the regular setting, Hennessy-Milner logic with recursion (recHML), a variant of the modal µ-calculus, provides a versatile back-end for expressing linear- and branching-time specifications. In this talk, I will discuss an extension of this logic that allows to express properties over data values (i.e. values from an infinite domain) and examine which fragments can be verified at runtime. Data values are manipulated through equality tests in modalities and through first-order quantification outside of them. They can also be stored using parameterised recursion variables.
I then examine what kind of properties can be monitored at runtime, depending on the monitor model. A key aspect is that the logic has close links with register automata with non-deterministic reassignment, which yields a monitor synthesis algorithm, and allows to derive impossibility results. In particular, contrary to the regular case, restricting to deterministic monitors strictly reduces the set of monitorable properties.
This is joint work with the MoVeMnt team (Reykjavik University): Luca Aceto, Antonis Achilleos, Duncan Paul Attard, Adrian Francalanza, Karoliina Lehtinen.
Traditionnellement, les bases de données suivent le modèle relationnel: les données sont rangées dans des tableaux et on utilise le langage de requête SQL afin d’en extraire de l’information. Depuis une quinzaine d’années, un autre type de modèles a commencé à être utilisé en pratique : le graphe de données. Les deux plus populaires sont le modèle de graphe à propriétés et le modèle RDF (Ressource Description Framework).
L’exposé se concentre sur les graphes à propriétés, en particuliers sur les langages de requêtes associés. La plupart des langages utilisés dans l’industrie sont fondés sur le formalisme théorique des RPQs (Regular Path Queries) qui permettent de naviguer dans le graphe en suivant une expression régulière. Néanmoins, chaque langage réel (PGQL, Cypher, GQL) utilise une sémantique fondamentalement différente de la sémantique traditionnelle des RPQs. On discutera de ces différences et de leurs conséquences.
Tous les dix ans approximativement, Java ajoute une grosse feature qui change un peu la façon dont on écrit le code. Une des idées actuelles est d’introduire le concept de programmation orientée donnée (Data Oriented Programming), basé sur le pattern matching, qui a pour but de simplifier la façon dont sont écrites les applications en Java.
Après un bref rappel de l’histoire de Java, ce sur quoi j’ai travaillé et ce sur quoi je travaille actuellement, je discuterai de la notion de programmation orientée donnée, de sa relation avec la programmation orientée objet. Puis je parlerais un peu plus en détail des différents challenges, actuels et à venir liés à l’introduction du pattern matching dans le langage Java.
On considère un automate aléatoire à n états, c’est à dire le choix de deux fonctions aléatoires uniformes a,b de [n] dans [n]. Un mot w est dit synchronisant (« reset word ») s’il existe un état v0 dans [n] tel qu’en lisant lettre-à-lettre le mot w depuis n’importe quel état, on arrive à l’état v0. On démontre une conjecture de Kisielewicz, Kowalski, Szykula (2013) selon laquelle, avec proba tendant vers 1, il existe un mot synchronisant de longueur au plus (√n)1+o(1). La meilleure borne connue était quasilinéaire (Nicaud, 2016). Cela repose sur un théorème de structure un peu étonnant qui dit qu’avec grande proba, il existe un mot w très court (de longueur seulement 1.01log(n)) tel que les w-transitions induisent un arbre. J’expliquerai l’heuristique de la preuve et j’en profiterai pour énoncer quelques questions ouvertes sur ces « w-arbres » que nous introduisons, dont notre preuve trop technique est loin de révéler tous les secrets. Travail commun avec Guillem Perarnau (Barcelone), https://arxiv.org/abs/2207.14108.