Abstract. TBA

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. TBA

Abstract. TBA

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]