Abstract. Nearly linear recurrences generalise linear recurrences and are special cases of linear time-invariant systems in control theory. In this talk, we formulate the Positivity Problem for such recurrences: given a recurrence and initial conditions, determine whether every satisfying sequence is nonnegative. This problem generalises the Positivity Problem for linear recurrence sequences and is a special case of the non-reachability problem for linear time-invariant systems. Our main contribution is a decision procedure for the Positivity Problem for order-2 recurrences. The termination proof of our procedure relies on a transcendence result for infinite series that is of independent interest.

Abstract. Hilbert's Basis Theorem underpins a considerable number of algorithmic results in algebraic geometry, by providing a termination argument. Instrumenting its use and deriving complexity upper bounds is however difficult.
Hilbert's Basis Theorem can be also seen as a consequence of Dickson's Lemma (1913) in well-quasi-order (wqo) theory, where generic complexity statements have been proven. The talk will present succinctly this wqo approach and apply it to a couple of known 'Ackermannian' complexity upper bounds: the zeroness problem for polynomial automata (by Benedikt et al., 2017), and Buchberger's algorithm for computing Gröbner bases (taking inspiration from Dubé et al., 1995).

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. This is joint work with Carine Pivoteau.

Abstract. Riemann-Roch spaces consist of functions whose zeros are imposed and whose poles can be predicted. Goppa codes are based on those functions as a way to generalise Reed-Solomon codes. They can also be used to perform additions in the Jacobian of a curve. I will present a deterministic algorithm computing a basis of a Riemman-Roch space associated to an arbitrary divisor of a curve. It results from arithmetic methods. We employ matrix reduction and the computation of integral bases of well-chosen fractional ideals of suitable Dedekind subrings of the curve’s function field. In particular, the OM algorithm for polynomial factorisation in local fields is needed to compute those bases.

Abstract. I'll present some results on the multiplicative structure of dual Goppa codes, in particular their decomposition into direct sums of geometric progressions with the same common ratio.
I'll explain how this allows to simplify or reinterpret some results related to the cryptanalysis of the McEliece system, such as my syzygy distinguisher, or also a recent key-recovery algorithm obtained jointly with P. Briaud, A. Lemoine, and J.-P. Tillich, whose asymptotic complexity heuristically seems to be subexponential in the error correcting capability of the underlying Goppa code.

Abstract. In computer algebra, efficient polynomial and matrix computations usually consist of two parts: fast multiplication algorithms (Karastuba's or FFT-based algorithms for polynomials, Strassen's and subsequent algorithms for matrices) and efficient reductions to multiplication. This provides fast algorithms for many polynomial and matrix computations (division, multipoint evaluation, interpolation, GCD computation, linear system solving, etc.). In terms of space complexity, fast multiplication algorithms as well as the reductions usually require at least a linear amount of extra space. On the other hand, the so-called naive algorithms of quadratic or cubic complexity only require constant space.
In this talk, I will describe recent results on the design of time- and space-efficient algorithms for polynomial and matrix computations. The goal is to provide fine-grained time-space complexity upper bounds for these problems. This requires a discussion of the models of space complexity for computing functions. In particular, cumulative algorithms such as $C += AB$ where the result has to be added to a nonzero value play a prominent role. We develop an automatic method to turn any bilinear accumulating algorithm to a constant-space variant with the same time complexity.
This is based on joint works with Pascal Giorgi (U. Montpellier), Daniel S. Roche (USNA, Annapolis) and Jean-Guillaume Dumas (U. Grenoble-Alpes).

Abstract. The Positivity Problem asks whether all the terms in a given sequence are non-negative. In this talk we shall focus on the open state of decidability of the Positivity Problem for the class of second-order P-finite sequences. Recall that a sequence is P-finite if it satisfies a linear recurrence relation with polynomial coefficients.
First, we will explain how the set of non-negative solutions to a given second-order recurrence relation are described by a system of linear inequalities. Second, we will see that the obstacle to deciding Positivity in this setting relates to the set of coefficients of the linear inequalities, which have a curious connection to continued fractions.

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