Duri Andrea Janett
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler--Leman abstract
Abstract:
We exhibit supercritical trade-off for monotone circuits, showing thatthere are functions computable by small circuits for which any circuitmust have depth super-linear or even super-polynomial in the number ofvariables, far exceeding the linear worst-case upper bound. We obtainsimilar trade-offs in proof complexity, where we establish the firstsize-depth trade-offs for cutting planes and resolution that are trulysupercritical, i.e., in terms of formula size rather than number ofvariables, and we also show supercritical trade-offs between width andsize for treelike resolution.Our results build on a new supercritical depth-width trade-off forresolution, obtained by refining and strengthening the compressionscheme for the Cop-Robber game in [Grohe, Lichter, Neuen & Schweitzer2023]. This yields robust supercritical trade-offs for dimension versusiteration number in the Weisfeiler--Leman algorithm. Our other resultsfollow from improved lifting theorems that might be of independent interest.This is joint work with Susanna F. de Rezende, Noah Fleming, JakobNordström and Shuo Pang.
11:00 • EPF Lausanne, INJ114
Dominique Manchon (CNRS et Université Clermont-Auvergne)
Post-groupes et algèbres post-Lie : une introduction abstract
Abstract:
Le algèbres post-Lie sont apparues en 2007 dans un article de B. Vallette sur l\'homologie des posets de partitions, et indépendemment, sous une forme légèrement différente, dans un travail de H. Munthe-Kaas et W. Wright sur la résolution numérique d\'équations différentielles sur un espace homogène. La notion récente de post-groupe 2023) est équivalente à deux notions plus anciennement établies : les groupes à deux étages ou skew-braces (2017) et les groupes tressés (2000). Elle est étroitement lie aux algèbres post-Lie, en ce sens que l\'algèbre de Lie d\'un post-groupe de Lie est une algèbre post-Lie.Je ferai un survol de ces notions, avant d\'aborder quelques résultats récemment obtenus avec M. J. H. Al-Kaabi, K. Ebrahimi-Fard, H. Munthe-Kaas et Lorenzo Zambotti.
14:00 • Université de Genève, Conseil Général 7-9, Room 1-05