Our seminar usually takes place the first and/or the second 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.
Next seminar:
- 23/4/2024:
Owen Garnier (Université de Picardie Jules Verne)
at Sophie Germain, room 1016, 10:30
Homology of categories and the Dehornoy-Lafont order complex
In this talk, I will first present two seemingly unrelated topics regarding homology computations. I will begin by detailing how one can use the homology of categories to compute group homology. Then, I will present the order complex of Dehornoy and Lafont, which is a general complex constructed for monoids satisfying combinatorial assumptions, and which gives a free resolution of the trivial module. I will also explain how to generalize the construction of the order complex to a category instead of a monoid, and how it allows for new homology computations.
As its name indicates, the order complex relies on some additional choice of an ordering on the associated category/monoid. I will finish by presenting a procedure for choosing a convenient order yielding a complex of smaller rank, thus facilitating actual computations.
Upcoming seminars:
- 7/5/2024:
TBA - 14/5/2024:
Alexandre Lê (Sorbonne University, Inria Paris, and Safran)
at Jussieu, room 15-25/502, 10:30
Previous seminars:
- 2/4/2024:
Djamel Eddine Amir (Loria, Nancy)
at Jussieu, room 15-16/413, 10:30
Computable Aspects of Topological Spaces
The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres, closed manifolds and finite graphs without endpoints : if a set X is homeomorphic to a sphere, a closed manifold or a such graph, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović and others in the recent years. We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. We study two families of topological invariants of low descriptive complexity, expressing the extensibility and the null-homotopy of continuous functions. We apply the theory to revisit previous results and obtain new ones. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs. - 12/3/2024
Antoine Béreau (CMAP École Polytechnique and Inria Saclay)
at Jussieu, room 15-16/413, 10:45
The Nullstellensatz and Positivstellensatz for Sparse Tropical Polynomial Systems
Grigoriev and Podolskii (2018) have established a tropical analogue of the effective Nullstellensatz, showing that a system of tropical polynomial equations is solvable if and only if a linearized system obtained from a truncated Macaulay matrix is solvable. They provided an upper bound of the minimal admissible truncation degree, as a function of the degrees of the tropical polynomials. We establish a tropical Nullstellensatz adapted to sparse tropical polynomial systems. Our approach is inspired by a construction of Canny-Emiris (1993), refined by Sturmfels (1994). This leads to an improved bound of the truncation degree, which coincides with the classical Macaulay degree in the case of n + 1 equations in n unknowns. We also establish a tropical Positivstellensatz, allowing one to decide the inclusion of tropical basic semialgebraic sets. This allows one to reduce decision problems for tropical semi-algebraic sets to the solution of systems of tropical linear equalities and inequalities. The later systems are known to be reducible to mean payoff games, which can be solved in practice, in a scalable way, by value or policy iteration methods. - 5/3/2024:
Joao Rafael de Melo Ruiz (Sorbonne University and Inria Paris)
at Jussieu, room 15-16/413, 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 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 is 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
Amibes d’hypersurfaces ou d’idéaux, approximation, contour et fonction de Ronkin, questions de stabilité
Je présenterai la notion d’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
