2024

Heure:	14:00 - 15:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Quelques progrès récents sur les fonctions G et les fonctions E
Description:	Javier Fresán Les fonctions G et les fonctions E sont des séries entières à coefficients algébriques qui sont solution d'une équation différentielle et satisfont à des conditions de croissance de nature arithmétique. Elles correspondent aux fonctions holonomes/D-finies qui apparaissent dans de nombreux problèmes en combinatoire, probabilité, physique. Elles ont été introduites dans le mémoire de Siegel sur les applications de l'approximation diophantienne en 1929, dans le but de généraliser les résultats de transcendence pour les valeurs de la fonction exponentielle en des arguments algébriques. Je survolerai de façon accessible quelques progrès récents, voire très récents, et moins récents sur les fonctions G et les fonctions E, en mettant l'accent sur deux questions : quelle est la structure de leurs équations différentielles ? quelle place occupent les fonctions hypergéométriques parmi elles ?

Heure:	11:00 - 12:00
Lieu:	Salle C308, Institut Galilée, Université de Villetaneuse
Résumé:	A Knowledge Compilation Take on Binary Boolean Optimization
Description:	Florent Capelli The Binary Boolean Optimization (BPO) problem aims at finding the maximal value that a rational polynomial P(x) can take when x is supposed to be a vector with 0 and 1 values. This non-linear optimization problem has recently received renewed attention. Current techniques for solving it either involve to solve a linear relaxation of the problem or use dedicated algorithm exploiting some structure in the way monomials are interacting with one another, allowing one to skip large parts of the search space compared to the brute force approach. In this talk, we present and explore the consequences of an interesting connection between BPO instances and another well studied problem on Boolean functions: the Algebraic Model Counting (AMC) problem. Given a Boolean function f on variables X and a weight on each of its variable, the AMC problem aims at finding the sum of the weights of every satisfying assignments of f. This problem can encode a lot of different tasks by simply changing the underlying algebraic structure where the sum and products are made. This way, we show how one can reformulate BPO instances as an AMC problem on an algebraic structure known as the (max,+)-semiring. The consequences of this connection are manyfold. In particular, we are able to recover every known results on the tractablability of BPO problem from this connection and the existing literature on the complexity of AMC. More importantly, this connection allows us to discover new tractable classes for BPO and is flexible enough so that we can find tractable instances of the slight variations of BPO such as BPO with cardinality constraints or pseudo-Boolean BPO, two problems for which few tractability results where known. More importantly, this approach yields practical results: by running a modified version of d4, a tool originally made for knowledge compilation, so that it performs AMC on the (max,+)-semiring instead, we show that our approach is competitive with the existing ones on hard instances. This talk will cover a gentle presentation of the BPO problem and its connection with AMC. We will then give a quick overview on existing techniques for solving AMC that are based on Knowledge Compilation and how this approach is fruitful for solving extensions of the BPO problem. We will conclude by a presentation of the way d4 works and of our practical results.