Abstract. Computing a Gröbner basis has been a fundamental task in computational algebra for more than 50 years. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. In this talk, I present a new paradigm for addressing such problems, i.e., a machine-learning approach using a Transformer model. This is a joint work with Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Yota Maeda, et Kazuhiro Yokoyama. The learning approach does not require an explicit algorithm design and can return the solutions in (roughly) constant time. This talk covers our initial results on this approach and relevant computational algebraic and machine learning challenges. In particular, the learning approach needs a large-scale dataset of couples of non-Gröbner sets and Gröbner bases generating the same ideal. This gives rise to underexplored open problems: the random generation of Gröbner bases and their ideal-invariant transformation into non-Gröbner sets, the structure of GL_n (k[X_1,...,X_n]) and its relation to effective version of the Quillen-Suslin theorem.

Abstract. Prince Rupert's problem asks which solids can pass through a hole cut in a congruent copy of themselves. While this curious question dates back to the 17th century, only recently has it been approached with computational and rigorous mathematical tools. In this talk, I will present a framework for deciding Rupert's property for convex polyhedra, based on geometric projections, optimization, and certified computation. I will recall results from 2021 proving that all Platonic solids and many Archimedean, Catalan, Johnson solids are Rupert, and then introduce the Noperthedron - the first known convex polyhedron that is not Rupert. I am going to outline the ideas behind the global and local theorems used in the proof and discuss the computational verification that establishes this counterexample.
This talk is based on joint work with Jakob Steininger.

Abstract. Analytic combinatorics studies asymptotic properties of families of combinatorial objects using complex analysis on their generating functions. In their reference book on the subject, Flajolet and Sedgewick describe a general approach that allows one to derive precise asymptotic expansions starting from systems of combinatorial equations. In the situation where the combinatorial system involves only cartesian products and disjoint unions, the generating functions satisfy polynomial systems with positivity constraints for which many results and algorithms are known. We extend these results to the general situation. This produces an almost complete algorithmic chain going from combinatorial systems to asymptotic expansions. Thus, it is possible to compute asymptotic expansions of all generating functions produced by the symbolic method of Flajolet and Sedgewick when they have algebraic-logarithmic singularities (which can be decided), under the assumption that Schanuel’s conjecture from number theory holds. That conjecture is not needed for systems that do not involve the constructions of sets and cycles. The talk is based on joint work with Carine Pivoteau.

Abstract. The central configurations of the Newtonian n-body problem are configurations of n point bodies, each with a positive mass, such that the Newtonian attraction may be exactly balanced by a centrifugal force. For example, a planar central configuration may rotate uniformly around its center of mass, thus defining a relative equilibrium of the n-body problem. Astronomical examples with n=3 are the Trojan asteroids and other bodies at some Lagrange point.
In 1995 I proved that there are only four types of central configurations of 4 bodies with equal masses, by using polynomial elimination. Here I wish to determine the central configurations of 5 bodies which have 3 bodies on a line. I will solve this problem in a symmetric case, where the existence result was published by Marian Gidea and Jaume Llibre in 2010, and independently by Kuo-Chang Chen and Jun-Shian Hsiao in 2011.

Abstract. We introduce a new family of rank metric codes. The construction of these codes relies on the "Chinese Remainder Theorem" for linearised polynomials. Linearised polynomials are polynomials in which the exponents of all the monomials are powers of q and the coefficients come from an extension field of the finite field of order q. The set of these polynomials forms a right Euclidean ring. We present the lifting of the isomorphism of the Chinese remainder theorem for linearised polynomials. We show how this lifting leads to a decoding algorithm for a special case of this family of codes: the case where the linearised polynomials have coefficients in the finite field of order q. (Joint work with Olivier Ruatta and Philippe Gaborit).
(The slides of this talk are available here.)

Abstract. We propose a new method for retrieving the algebraic structure of a generic alternant code given an arbitrary generator matrix, provided certain conditions are met. We then discuss how this challenges the security of the McEliece cryptosystem instantiated with this family of codes. The central object of our work is the quadratic hull related to a linear code, defined as the intersection of all quadrics passing through the columns of a given generator or parity-check matrix, where the columns are considered as points in the affine or projective space. The geometric properties of this object reveal important information about the internal algebraic structure of the code. This is particularly evident in the case of generalized Reed-Solomon codes, whose quadratic hull is deeply linked to a well-known algebraic variety called the rational normal curve. By utilizing the concept of Weil restriction of affine varieties, we demonstrate that the quadratic hull of a generic dual alternant code inherits many interesting features from the rational normal curve, on account of the fact that alternant codes are subfield-subcodes of generalized Reed-Solomon codes. If the rate of the generic alternant code is sufficiently high, this allows us to construct a polynomial-time algorithm for retrieving the underlying generalized Reed-Solomon code from which the alternant code is defined, which leads to an efficient key-recovery attack against the McEliece cryptosystem when instantiated with this class of codes. Finally, we discuss the generalization of this approach to Algebraic-Geometry codes and Goppa codes.
(The slides of this talk are available here.)

Abstract. Algbraic invariants plays a cental role in program analysis and verification, they provide a compact certificate for corrctness. A natural way to study them is through the algebraic closure of matrix monoids, which captures all the polynomial relations satisfied by the reachable configurations of linear or affine programs. Recent results show that given a finite set of rational matrices, the algebraic closure of the monoid they generate is effectively computable. This opens up new directions, ranging from the complexity of computing invariants to structural questions about orbit closures and algebraic groups. In this talk I will survey some of these problems and the techniques used to tackle them. I will begin with a polynomial-time algorithm for computing closures in the case of a single matrix, before moving on to the general case. I will then discuss the “reverse problem” for commutative matrices: given a set of polynomials, does their ideal define the orbit closure of an algebraic group? Finally, I will touch on connections with reachability and closure problems in one-counter systems (1-VASS). This talk is based on the following papers: arXiv:2407.09154, arXiv:2407.04626, arXiv:2507.09373.

Abstract. We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input word. P-finite automata can also be viewed as simple tail-recursive programs in which the arguments of recursive calls can non-linearly refer to a variable that counts the number of recursive calls. The nomenclature is motivated by the fact that over a unary alphabet P-finite automata compute so-called P-finite sequences, that is, sequences that satisfy a linear recurrence with polynomial coefficients. Our main result shows that P-finite automata can be learned in polynomial time in Angluin's MAT exact learning model. This generalises the classical results that deterministic finite automata and weighted automata over a field are respectively polynomial-time learnable in the MAT model.

Abstract. In arithmetic geometry, Artin-Schreier-Witt theory gives a way to construct unramified covers of curves. However, nobody has ever made a full computation using these techniques. In this talk, we will explain how we implemented an algorithm which enables one to compute such covers. I will explain the motivation behind this problem, and the challenges that one faces using this theory. For our computations, it is necessary to have an algorithm which computes the fixed points of a Frobenius-semilinear map. I will also explain how to implement such an algorithm. This is a joint work with Christophe Levrat (Inria Saclay).

Abstract. Differential and difference algebra studies the algebraic aspect of differential and difference equations, which provides an algebraic foundation for symbolic computation of differential and difference equations. In this talk, we will first introduce a stability problem in differential and difference fields. Secondly, we present some stability criteria for several classes of special functions. At the end of this talk, we will prove that all D-finite functions or P-recursive sequences are eventually stable.
(The slides of this talk are available here.)

Abstract. This informal presentation provides an overview of the current state of small fast matrix multiplication algorithm development. We focus on finding compact rank tensor decompositions related to the bilinear map that computes the product of n×p and p×q matrices, where n,p and q are all less than 32. We review the main methods currently employed to construct the decompositions (with the smallest known tensor rank) and highlight the limitations of these approaches.

Abstract. Differential algebra is the branch of algebra that studies differential equations from an algebraic standpoint,inspired by the way polynomial equation are studied using algebraic geometry.
A key topic in this field is the elimination of variables. More precisely, given a system with several variables, we aim to describe the differential relations satisfied by a selected subset of those variables. Elimination is used to analyze systems of differential equations, especially in the context of dynamical systems models where data is available only for a subset of the variables.
In this talk, we provide an overview of existing tools for differential elimination and discuss their potential applications. We present our main result: the characterization of the set of terms that can appear in the resulting polynomial after elimination. Based on this result, we introduce an algorithm and demonstrate that our implementation can handle problems that are beyond the capabilities of current state-of-the-art software for differential elimination. We also discuss a new approach to computing so-called mixed fiber polytopes in the context of polynomial elimination. We demonstrate the practical performance improvements of our algorithm compared to existing methods and highlight an application of this work to differential elimination.
Joint works with Gleb Pogudin and Rafael Mohr.

Abstract. Let L be a language over a finite set of symbols, and let f be a mapping that assigns to each string of symbols a square matrix with rational entries in a way that respects concatenation. We are interested in whether it is possible to effectively compute the algebraic closure of the set of matrices generated by applying f to all strings in the language. It was recently shown that this closure can be computed when the language is regular.
In this talk, we show the computability of this closure for 1-VASS coverability and reachability languages, and we discuss extensions of these results to families of context-free languages. Mainly, I will focus on languages determined by finite-index grammars.
This work is in collaboration with Rida Ait El Manssour, Mahsa Shirmohammadi, and James Worrell; and is published in SODA 2026.

Abstract. Consider three univariate polynomials P, Q, R in (ℤ/r ℤ)[x], for some integer r > 1. The problem of modular composition is to compute the composition P ∘ Q modulo R. In our talk, we will present a new algorithm for this task, with a better bit complexity than all previously known algorithms.

Abstract. There have been several works recently on getting sharper upper bounds for the tensor rank of matrix multiplication tensors for small and specific matrix formats. One of the techniques applied in this context is the flip graph method introduced by Jakob Moosbauer and the speaker at ISSAC'23. In the talk, we will explain this method, discuss its pros and cons, and summarize the results we obtained with it so far.

Abstract. The complexity of many algebraic algorithms for solving non-linear polynomial systems of equations over finite fields such as the XL (eXtended Linearization) algorithm or variants of the F4/F5 algorithms is directly determined by the so called degree of regularity. In essence, we need to form a Macaulay matrix at this degree, which can be thought of as the linearization of monomial multiples of the polynomials from the problem instance, and then solve the obtained linear system. Although the degree of regularity guarantees we can solve the system, it is a rather coarse parameter. This means that sometimes, we end up with a heavily overdetermined Macaulay matrix in order to provably deal with underdeterminedness in a lower degree. In this talk I will present a technique that reduces this inherent coarseness, and with this also reduces time and memory complexity. The technique can be seen as a way of ``smoothing'' the degree of regularity i.e. operating at a degree in-between two integer values. Instead of the full Macaulay matrix, we consider specific submatrices that we show are sufficient to solve the given system. Under a mild assumption that generalizes the notion of semi-regularity, which we experimentally verify for a range of parameters, we show the validity of our approach. This is a joint work with Sam Jaques, Lars Ran and Melvin Seitner.
(The slides of this talk are available here.)

Archive [2019-2021] [2021-2024] [2024-2025]