Our seminar *usually* takes place the first and/or Tuesday of every month

(but we might also meet in between, should an opportunity arises)

*Members of our team also participate to the monthly AFRIMath seminar on geometry and topology. *

- 5/2/2024:

Joao Rafael de Melo Ruiz (Sorbonne University and Inria Paris)

at Jussieu, room TBA, 10:30*Reading Rational Univariate Representations from Lexicographic Gröbner bases*

In the context of calculation a Rational Univariate Representation (RUR) of a zero-dimensional system over a field K, it is necessary to certify a that a chosen linear form separates the solution set, and then use that form to calculate the polynomials in the RUR. The main result we found is that both of these can be simply « read » from the coefficients of some lexicographic Gröbner bases. This approach works even if the ideal in question has no particular structure (such as being in shape position or having a cyclic quotient algebra). Implementing this principle in Maple and in Julia has shown that this approach competitive with the state-of-the-art algorithms, even before performing more sophisticated optimizations. - 6/2/2024 :
**CANCELLED***(postponed for a future day)*

Xavier Allamigeon (Inria Saclay and École Polytechnique)

at Jussieu, room 15-16/413, 10:30*No self-concordant barrier interior point method is strongly polynomial*

A long-standing question has been to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative.

In this talk, I will show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, for convex optimization problems, the image under the logarithmic map of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. This curve, called the tropical central path, has a strong connection with the simplex method in the case of LP. I will provide an explicit linear program that falls in the same class as the Klee-Minty counterexample, i.e., a combinatorial n-cube for which interior-point methods require at least 2^n-1 iterations.

This is a joint work with Stéphane Gaubert and Nicolas Vandame (Inria and Ecole Polytechnique). - 23/1/2024 :

Franck Sueur (Institut de Mathématiques de Bordeaux)

at Jussieu, room 15-16/413, 10:30*Differential transmutations*

Inspired by Gromov’s partial differential relations, we introduce a notion of differential transmutation, which allows to transfer some local properties of solutions of a PDE to solutions of another PDE, in particular local solvability, hypoellipticity, weak and strong unique continuation properties and the Runge approximation property. The latest refers to the possibility to approximate some given local solutions by a global solution, with point controls at preassigned positions in the holes of the initial domain. As an example we consider the steady Stokes system, which can be obtained as a differential transmutation of an appropriate tensorization of the Laplace operator.

- 12/12/2023 :

Antonios Varvitsiotis (Singapore University of Technology and Design)

at Jussieu, room 15-25/502, 10:00

*Identifying and controlling agent behavior in games using limited data*Decentralized learning algorithms are an essential tool for designing multi-agent systems, as they enable agents to autonomously learn from their experience and past interactions. In this work, we propose a theoretical and algorithmic framework for real-time identification of the learning dynamics that govern agent behavior in games using a short burst of a single trajectory. Our method identifies agent dynamics through polynomial regression, where we compensate for limited data by incorporating side-information constraints that capture fundamental assumptions or expectations about agent behavior, e.g., agents tend to move towards directions of improving utility. These constraints are enforced computationally using sum-of-squares optimization, leading to a hierarchy of increasingly better approximations of the true agent dynamics. Extensive experiments demonstrate that our approach accurately recovers the true dynamics across various games and target learning dynamics while using only five samples from a short run of a single trajectory. Notably, we use strong benchmarks such as predicting equilibrium selection as well as the evolution of chaotic systems for up to ten Lyapunov times.

Based on joint work with I. Canyakmaz, G. Piliouras and J. Sakos.

Alain Yger (Institut de Mathématiques de Bordeaux)

at Jussieu, room 15-25/502, 11:00

Je présenterai la notion d’*Amibes d’hypersurfaces ou d’idéaux, approximation, contour et fonction de Ronkin, questions de stabilité**amibe*attachée à une hypersurface

algébrique du tore complexe $(\mathbb C^*)^n$, voire à un idéal de

$\mathbb C[X_1^{\pm 1},…,X_n^{\pm 1}]$, ainsi ses approximations

géométriques telles que déecrites par Kevin Purbhoo en 2008, en

lien avec la notion de*d\’eséquilibre*(”lobsideness”)

inhérente à un*polynôme*de Laurent en $n$ variables (inspirée du

contexte $p$-adique, puis transcrite dans le contexte archimédien).

J’insisterai sur la notion d’application de Gauss, et, avec elle, de*contour d’amibe*, contour dont le tracé implique la théorie

algébrique de l’élimination, ainsi que sur la fonction de Ronkin,

fonction convexe attachée à un polynôme de Laurent en $n$

variables et dont l’approximation par les sommes de Riemann implique la

FFT. C’est dans le cadre du lien entre ces sommes de Riemann et

l’approximation géométrique de l’amibe ou de son squelette que se

situent les résultats établis avec B. Bossoto et M. Mboup concernant

les tests (probabilistes) de stabilité de filtres rationnels. Je

mentionnerai aussi comment reformuler le ”polydisk nullstellensatz”

dans un tel cadre. - 07/11/2023 : Aurélien Gribinski (Inria Paris and IMJ-PRG)

at Jussieu, room 15-16/413, 10:00*An introduction to finite free probability through the lens of entropy*

We will explain how polynomials can be looked at as random variables. More specifically, we will explain how we can associate moment generating functions to them, derive a law of large numbers or a central limit theorem, and we will specifically focus on a natural notion of entropy that leads to nontrivial inequalities and monotonicity of discriminants. - 19/10/2023 : Carles Checa (University of Athens)

at Jussieu, room 15-16/101, 10:00*Regularity, Gröbner bases and computations with multi-homogeneous polynomial systems*

In this talk, we will review the relevance of regularity as an invariant that governs the computations with polynomial systems. We will motivate the relevance of Gröbner basis through classical problems in algebraic geometry such as the ideal membership problem and we will describe the main results (mainly due to Bayer and Stillman) relating the regularity of the ideal and the cost of building Gröbner bases. Next, we will describe the setting of multi-homogeneous polynomial systems that appear in applications and explain some of the our results describing Gröbner bases in this context.

This is joint on-going work with Matías Bender, Laurent Busé, and Elias Tsigaridas. - 3/10/2023 : Jean Michel (IMJ-PRG)

at Sophie Germain, room 1016*Introduction to Julia*