| Links' Seminars and Public Events |   |
| 2022 | |
|---|---|
Fri 25th Feb 11:00 am 12:00 pm | Séminaire Nico |
Fri 28th Jan 11:00 am 12:00 pm | Alexandre Vigny (visio) Title: Separator logic, expressive power and algorithmic applications Abstract: First-order logic (FO) can express many algorithmic problems on graphs, but fails to express whether two vertices are connected. We define a new logic (separator logic) by enriching FO with connectivity predicates connk(x, y, z1, . . . , zk) that hold true in a graph if there exists a path between x and y after deletion of z1, . . . , zk. In this talk I will first present a study of the expressive power of this new logic. I will then present algorithmic results for this logic on graph classes that exclude a topological minor. These results were obtained in collaboration with Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, and Szymon Toruńczyk. |
Fri 21st Jan 11:00 am 12:00 pm | Aurélien Lemay in Seminar |
| 2021 | |
Fri 10th Dec 11:00 am 12:00 pm | Séminaire Sebastien Tavenas Title: Bornes inférieures superpolynomiales pour les circuits de profondeur constante Abstract: Tout polynôme multivarié P(X_1,...,X_n) peut être écrit comme une somme de monômes, i.e., une somme de produits de variables et de constantes du corps. La taille naturelle d'une telle expression est le nombre de monômes. Mais, que se passe-t-il si on rajoute un nouveau niveau de complexité en considérant les expressions de la forme : somme de produits de sommes (de variables et de constantes) ? Maintenant, il devient moins clair comment montrer qu'un polynôme donné n'a pas de petite expression. Dans cet exposé nous résoudrons exactement ce problème. Plus précisément, nous prouvons que certains polynômes explicites n'ont pas de représentations "somme de produits de sommes'' (SPS) de taille polynomiale. Nous pouvons aussi obtenir des résultats similaires pour les SPSP, SPSPS, etc... pour toutes les expressions de profondeur constante. " |
Thu 25th Nov 2:00 pm 3:00 pm | Nofar Carmeli in Links' Seminar |
Fri 29th Oct 11:00 am 12:00 pm | Séminaire Antoine Amarilli |
Fri 22nd Oct 11:00 am 12:00 pm | Mikaël Monet in Links' Seminar |
Fri 15th Oct 11:00 am 12:00 pm | Claire Soyez-Martin in Links' seminar |
Fri 17th Sep 11:00 am 12:00 pm | Séminaire Corentin Barloy Title: Stackless Processing of Streamed Trees Abstract: Processing tree-structured data in the streaming model is a chal-lenge: capturing regular properties of streamed trees by means of astack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly—with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ. Link: paperman.name/data/pub.....0.pdf  lille-Salle |
Fri 10th Sep 10:00 am 11:00 am | Séminaire de Patrick Baillot titre: Type-based complexity analysis in a parallel process calculus Abstract: Some type systems have been designed to analyse statically the time coplexity of functional languages. A natural question is whether this approach can be extended to parallel languages. We address this problem for the Pi-calculus, a paradigmatic calculus for parallel and concurrent computation. In Pi-calculus, processes communicate through channels that can carry values and channel names. We will define notions of sequential and parallel complexity for Pi-calculus, and present a type system that provides an upper bound on the time complexity of processes. This is based on joint work with Alexis Ghyselen (ESOP 2021). Based on: link.springer.com/chap.....9-3_3 |
