| Links' Seminars and Public Events |   |
| 2022 | |
|---|---|
Fri 1st Jul 11:00 am 12:00 pm | Séminaire Arnaud Durand |
Fri 10th Jun 10:00 am 11:00 am | Séminaire Corentin Barloy Title:The Regular Languages of First-Order Logic with One Alternation Abstract: The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary Σ2 formula defines a regular language with a neutral letter, then there is an equivalent Σ2 formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for Σ2 over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest. |
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. " |
