- 2021-09-24: 11:00: Georgy Scholten (Sorbonne Univ., LIP6),
Truncated Moment Cone and Connections to the Coalescence Manifold.
We study the univariate moment problem of piecewise-constant density functions
on the interval $[0, 1]$ and its consequences for an inference problem in
population genetics. We show that, up to closure, any collection of n moments is
achieved by a step function with at most $n-1$ breakpoints and that this bound is
tight. We use this to show that any point in the $n$-th coalescence manifold in
population genetics can be attained by a piecewise constant population history
with at most $n-2$ changes. We give a semi-algebraic description of the n-th
coalescence manifold as a projected spectrahedron.
- 2021-06-18: 11:00: Bruno Salvy (Inria, LIP, ENS-Lyon),
Effective coefficient asymptotics of multivariate rational functions via
semi-numerical algorithms for polynomial systems,
slides.
The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables. This is joint work with Stephen Melczer.
- 2021-05-21: 11:00: Didier Henrion (LAAS-CNRS Toulouse and Czech Tech. Univ. Prague),
Accelerating the moment-SOS hierarchy for volume approximation,
slides.
The moment-SOS hierarchy can be used to approximate numerically the
volume of a semialgebraic set $X$ at the price of solving increasingly large
convex optimization problems. In its original form, the dual SOS problem in
the hierarchy consists of approximating from above the indicator function of $X$
with a polynomial of increasing degree, thereby suffering from the Gibbs
effect (large overshoots near the discontinuity points). In this talk we
explain how to suppress this effect by adding redundant linear constraints in
the primal moment problem. These constraints are a consequence of Stokes'
theorem. This results in a significant acceleration of the hierarchy. This is
joint work with Matteo Tacchi and Jean Bernard Lasserre, see
arXiv:2009.12139 or
hal:02947268.
- 2021-05-07: 11:00: Pierre Vanhove
(CEA, France, and HSE University, Moscow, Russia),
Picard-Fuchs equations for Feynman integrals,
slides.
In this talk we will present various methods for computing the Picard-Fuchs equations for Feynman integrals that arise in quantum field theory. After reviewing the main properties of Feynman integrals, we will discuss two methods for deriving their ideal of differential equations, a first one using the Gel'fand-Kapranov-Zelevinsky construction and the other one using the creative telescoping. In this talk we will compare the two approaches and give a physical intepretation of the certificate.
This based on some work done in collaboration with Charles Doran and Andrey Novoseltsev.
- 2021-04-09: 16:00: Virginia Vassilevska Williams (MIT, USA),
A refined laser method and faster matrix multiplication,
slides.
The complexity of matrix multiplication is measured in terms of $\omega$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{\omega+\epsilon})$ field operations for all $\epsilon>0$; the best bound until now is $\omega<2.37287$ [Le Gall'14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the “value” of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date:
$\omega<2.37286$.
The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.
(Joint work with Josh Alman.)
- 2021-04-02: 11:00: Manfred
Buchacher (Johannes Kepler Universität, Linz),
Separating variables in bivariate polynomial ideals,
slides.
We present an algorithm which for any given ideal $I \subseteq \mathbb{K}[x,y]$ computes
$I \cap (\mathbb{K}[x] + \mathbb{K}[y])$. Our motivation for looking at the problem came from enumerative
combinatorics in the context of lattice walks: an elimination of this kind appears in Bousquet-Mélou’s proof of
the algebraicity of the
generating function of Gessel’s walks. The problem also arises when one wants to compute the intersection of two
$\mathbb {K}$-algebras. This is joint work with Manuel Kauers and Gleb Pogudin.
- 2021-03-12: 15:00:
Bernd Sturmfels (UC Berkerley, USA, and MPI Leipzig, Germany),
Linear PDE with constant coefficients,
slides.
We discuss algebraic methods for solving systems of homogeneous
linear partial differential equations with constant coefficients. The setting is the
Fundamental Principle established by Ehrenpreis and Palamodov in the 1960’s.
Our approach rests on recent advances in commutative algebra, and it offers new
vistas on schemes and coherent sheaves in computational algebraic geometry.
- 2021-02-26: 11:00:
Philippe Moustrou (University of Tromsø, Norway),
Symmetric situations in polynomial optimization,
slides.
In the first part of the talk, we will discuss symmetric polynomial
ideals, namely ideals of polynomials closed under permutations of
variables. The Specht polynomials are fundamental in the
understanding of the representations of the symmetric group. We show a
connection between the leading monomials of polynomials in a symmetric
ideal and the Specht polynomials contained in the ideal. This
provides applications in several contexts, in particular for
algorithmic purposes. Most notably, this connection gives information
about the points in the corresponding algebraic variety. From another
perspective, it restricts the isotypic decomposition of the ideal
viewed as a representation of the symmetric group.This allows further
algorithmic consequences, in particular for non-negativity
certifications of symmetric polynomials on symmetric variety via sums
of squares.
Besides sums of squares, alternative methods have been recently
introduced to certify the non-negaitivity of polynomials. The second
part of the talk will focus on methods based on Sums of
Arithmetic-Geometric Exponentials (SAGE) and Sums Of Non-negative
Circuit polynomials (SONC) for symmetric polynomials. We will discuss
the theoretical aspects such as the comparison between these cones and
the cone of non-negative symmetric polynomials, as well as
symmetry-reduction techniques for the corresponding algorithms.
Based on joint works with Helen Naumann, Cordian Riener, Thorsten
Theobald and Hugues Verdure.
- 2021-02-19: 11:00:
Ilaria Zappatore (INRIA Saclay).
Simultaneous rational function reconstruction and applications to algebraic coding theory,
slides.
The simultaneous rational function reconstruction (SRFR) is the
problem of reconstructing a vector of rational functions with the same
denominator given its evaluations (or more generally given its
remainders modulo different polynomials).
The peculiarity of this problem consists in the fact that the common
denominator constraint reduces the number of evaluation points needed
to guarantee the existence of a solution, possibly losing the
uniqueness.
One of the main contributions presented in this talk consists in the
proof that uniqueness is guaranteed for almost all instances
of this problem.
This result was obtained by elaborating some other contributions and
techniques derived by the applications of SRFR, from the polynomial
linear system solving to the decoding of Interleaved Reed-Solomon
codes.
In this talk it is also presented another application of the SRFR
problem, concerning the problem of
constructing fault-tolerant algorithms:
algorithms resilients to computational errors.
These algorithms are constructed by introducing redundancy and using
error correcting codes tools to detect and possibly correct errors
which occur during computations. In this application context, we
improve an existing fault-tolerant technique for polynomial linear
system solving by interpolation-evaluation, by focusing on the related
SRFR.
Contains joint works with Eleonora Guerrini and Romain Lebreton.
- 2021-02-12: 11:00:
Thibaut Verron (Johannes Kepler Universität, Linz, Austria),
Gröbner bases in Tate algebras,
slides.
Tate series are a generalization of polynomials introduced by John
Tate in 1962, when defining a $p$-adic analogue of the correspondence
between algebraic geometry and analytic geometry. This $p$-adic
analogue is called rigid geometry, and Tate series, similar to
analytic functions in the complex case, are its fundamental
objects. Tate series are defined as multivariate formal power series
over a $p$-adic ring or field, with a convergence condition on a closed
ball.
Tate series are naturally approximated by multivariate polynomials
over $\mathbb{F}_p$ or $\mathbb{Z}/p^n \mathbb{Z}$, and it is possible
to define a theory of Gröbner bases for ideals of Tate series,
which opens the way towards effective rigid geometry. In this talk, I
will present those definitions, as well as different algorithms to
compute Gröbner bases for Tate series.
Joint work with Xavier Caruso and Tristan Vaccon.
- 2021-02-04: 14:00:
Simon Abelard (LIX, École polytechnique),
Structured algorithms for algebraic curves,
slides.
In this talk we will discuss two different algorithmic problems
related to algebraic curves : counting points and computing
Riemann-Roch spaces, both of them having applications in various
fields of computer science such as cryptography and coding
theory. These tasks are actually closely related to well-known
problems from computer algebra.
The first problem mostly boils down to solving polynomial systems. We
will see how the underlying structure of these systems helps to derive
better complexity bounds and to perform practical computations.
For the second problem, previous algorithms (Khuri-Makdisi in 2007, Le
Gluher and Spaenlehauer in 2018) compute Riemann-Roch spaces through
the use of linear algebra. The main novelty of our work is to rely on
a $K[X]$-module structure instead so that we can replace linear
algebra by faster algorithms for computing interpolation bases (such
as the one of Neiger in 2016), thus deriving a subquadratic complexity
bound. We will also talk about the ongoing implementation of this
algorithm.
The first part of the talk contains joint work with P. Gaudry and
P.-J. Spaenlehauer, the second part is joint work with A. Couvreur
and G. Lecerf.
- 2021-01-22:
Rémi Imbach (Courant Institute, New York University, USA),
Complex roots clustering.
We are interested in computing clusters of complex roots of
polynomials and square polynomials systems. Root clustering differs of
root isolation in that it can be performed softly, i.e. avoiding some
decisions of zero. This allows clustering algorithms to be robust to
multiple roots and to accept inputs given by black boxes for
approximation, for instance polynomials which coefficients are in
towers of field extensions. The starting point of our talk is the
existence of a clustering algorithm for roots of univariate
polynomials. We will show how this algorithm can be embedded in an
algorithm for computing clusters of roots of triangular systems of
polynomials resulting in particular of a symbolic step to process
non-triangular systems. We will also present recent practical
improvements for the univariate case.