| 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. " |
