Abstract. A posteriori validation methods based on fixed-point theorems are used extensively in the field of validated numerics. In most cases, the problem is locally invertible around the solution and tight error bounds can be obtained by using a Newton(-like) operator. For singular (and thus degenerate) problems, however, one typically needs to solve overdetermined systems rigorously, which admit no solution under generic, arbitrarily small perturbations. Therefore, even properly specifying what a validation algorithm should validate in such cases is a nontrivial question. In this talk, we will illustrate this challenge for degenerate polynomial root-finding in two cases.
The first case is classical root-finding for univariate polynomials over K = R or C, in presence of multiple roots. Multiple roots are already an important issue for numerical (i.e., non-validated) solvers, due to the ill-conditioning around the zeros of the derivative of the polynomial. After explaining what "validating multiple roots" of a polynomial given with interval coefficients should mean, we will present a validation algorithm [1] inspired from Zeng's numerical routine to detect and approximate such roots efficiently [2].
Second, we consider bivariate polynomials P(x,y), seen as polynomials in y with coefficients in K[x]. If the point x0 is singular (meaning that P(x0,y), as a univariate polynomial in y, has multiple roots), then the solutions y(x) to P(x,y)=0 above x=x0 must be sought under the form of Puiseux series, i.e., power series in x-x0 with fractional exponents of bounded denominators. It is well-known that Puiseux series solutions can be computed exactly via the Newton-Puiseux algorithm, but the size of the symbolic representations of the coefficients makes it often too costly. An alternative strategy proposed by Poteaux and Rybowicz [3] is to obtain the structure of the series solutions via a symbolic execution of Newton-Puiseux modulo a well-chosen prime number, and then using numerical methods guided by this structure to recover the coefficients. This is where validated numerics comes into play. A cornerstone routine for this is a validated numerical Hensel's lifting [4] to rigorously lift a univariate factorization of P(x0,y)=0 into a bivariate factorization of P(x,y)=0. More generally, designing a suitable fixed-point argument for this problem requires understanding the "multiplicity structure" of the roots, which is more subtle than for univariate polynomials since two distinct roots y_1(x) and y_2(x) may coincide up to some power of x-x0 and hence look like a double root.
This is a joint work still in progress with Adrien Poteaux, in collaboration with intern students: Léo Soudant, Jasmin Krüger and Arthur Vinciguerra.
[1] Florent Bréhard, Adrien Poteaux and Léo Soudant. Validated Root Enclosures for Interval Polynomials with Multiplicities. In : Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC). 2023. p. 90-99. available at: https://hal.science/hal-04138791/
[2] Zhonggang Zeng. Computing multiple roots of inexact polynomials. Mathematics of Computation, 2005, vol. 74, no 250, p. 869-903. available at: https://www.ams.org/journals/mcom/2005-74-250/S0025-5718-04-01692-8/
[3] Adrien Poteaux and Marc Rybowicz. Good reduction of Puiseux series and applications. Journal of Symbolic Computation, 2012, vol. 47, no 1, p. 32-63. available at: https://hal.science/hal-00825850/
[4] Florent Bréhard, Jasmin Krüger, Adrien Poteaux and Arthur Vinciguerra. Validated numerical Hensel lifting. Abstract submitted at the 2024 Conference on Computer Algebra in Scientific Computing (CASC). 2024. available at: https://hal.science/hal-04626388/

Abstract. Computational problems concerning the orbit of a point under the action of a matrix group occur in numerous subfields of computer science, including complexity theory, program analysis, quantum computation, and automata theory. In many cases the focus extends beyond orbits proper to orbit closures under a suitable topology. Typically one starts from a group and several points and asks questions about the orbit closure of the points under the action of the group, e.g., whether two given orbit closures intersect.
In this talk, I will introduce and motivate several problems involving groups and orbit closures, focusing on computation and determination tasks. In regards to computation, we are given a set of matrices and tasked with computing the defining ideal of the algebraic group generated by those matrices. The determination task, on the other hand, involves starting with a given variety and determining whether and how it can be represented as an algebraic group or an orbit closure. The "how" question often asks whether the underlying group can be topologically generated by s matrices for a given s.
The talk is based on several joint works:
https://dl.acm.org/doi/10.1145/3476446.3536172
https://arxiv.org/abs/2407.04626
https://arxiv.org/abs/2407.09154

Abstract. On présente un nouveau distingueur pour les codes alternants et de Goppa, dont la complexité asymptotique est sous-exponentielle en la capacité de correction --- donc meilleure que celle des algorithmes de décodage génériques. De plus, il s'affranchit des fortes contraintes sur les paramètres nécessaires à d'autres distingueurs ou algorithmes de reconstruction structurelle récents : en particulier, il fonctionne (théoriquement) sur les codes utilisés par le candidat Classic McEliece à la standardisation en cryptographie post-quantique. Les invariants qui servent à distinguer sont les nombres de Betti gradués de l'anneau de coordonnées homogènes d'un raccourci du code dual. Depuis son introduction en 1978, c'est la première fois qu'une analyse du système de McEliece franchit cette barrière exponentielle.

Abstract.

Abstract.

La topologie d'une variété algébrique complexe (non singulière) est basiquement déterminée par les degrés de ses équations. Ce n'est pas le cas s'agissant des variétés algébriques réelles. Typiquement, si les équations comportent peu de monômes (de degrés aussi grands soient-ils) alors la topologie de la variété algébrique réelle sera faible (par exemple son nombre de composantes connexes sera petit). La théorie des Fewnomials initiée par Khovanskii donne des bornes explicites pour cette topologie en fonction des nombres de monômes et nombres de variables. Dans cet exposé j'essaierai de présenter les résultats principaux de cette théorie ainsi que les dernières généralisations au cas multivarié de la règle de Descartes qui est à la base de cette théorie.

Abstract. Understanding the geometric properties of gradient descent dynamics is a key ingredient in deciphering the recent success of very large machine learning models. A striking observation is that trained over-parameterized models retain some properties of the optimization initialization. This “implicit bias” is believed to be responsible for some favorable properties of the trained models and could explain their good generalization properties. In this work, we expose the definitions and properties of "conservation laws", that define quantities conserved during gradient flows of a given machine learning model, such as a ReLU network, with any training data and any loss. After explaining how to find the maximal number of independent conservation laws via Lie algebra computations, we provide algorithms to compute a family of polynomial laws, as well as to compute the number of (not necessarily polynomial) conservation laws. We obtain that, on a number of network architectures, there are no more laws than the known ones. We also identify new laws for certain flows with momentum and/or non-Euclidean geometries.
Joint work with Sibylle Marcotte and Gabriel Peyré

Abstract. We investigate a class of deterministic auctions, which were introduced by Giannakopoulos and Koutsoupias (2018) as "Straight-Jacket Auctions (SJA)" in the context of revenue maximization. The resulting prizes can be described in terms of parameterized volumes of some family of convex polytopes, and these volumes can be computed via solving systems of polynomial equations. We obtain an optimality result for SJA among certain deterministic auctions. Moreover, we employ the computer algebra system OSCAR to explicitly determine the optimal prices and revenues.
Joint work with Max Klimm and Sylvain Spitz.

Abstract. The linear complementarity problem LCP(M,q) asks, for a given vector q, whether there exists a pair of vectors (w,z) satisfying w - M z = q, w,z >= 0, and w.z = 0. M is said to be a Q-matrix when a solution exists for all q. Since the fifties, we do know exactly what conditions the matrix M has to satisfy for the existence and uniqueness of solutions for all q. The problem remains however open when dropping uniqueness and offers a typical instance of a quantifier elimination problem beyond the capabilities of the state-of-the-art implementations of the CAD even for dimension 3. In this talk, I will expose the inherent difficulty of characterizing Q-matrices by reformulating the problem as a covering problem of the Euclidean space. I will then focus on the regions where no solution exists (so called holes) and show that they only occur in specific locations. This insight is then exploited to fully characterize planar and spatial Q-matrices via a local reduction around the vectors defining the problem. In particular, we fully solve the problem for n=3 and show the actual solution provided by our implementation.
This is a joint work with Christelle Kozaily.

Archive [2019-2021] [2021-2024]