This seminar focuses mainly on computer algebra algorithms and implementations for solving mathematical problems exactly, with a special focus on polynomial system solving and its broad range of applications.
Among others, topics which are covered are:To receive further anouncements, register for the mailing list here:
Multiplication in finite fields with
Chudnovsky-type algorithms over the projective line,
Bastien
Pacifico,
I2M, Aix Marseille Université.
TBD,
Erik
Panzer,
Mathematical Institute, University of Oxford.
Thematic program on Recent Trends in Computer Algebra.
Thematic program at Institut Henri Poincaré on post-quantum algebraic cryptography.
10 December 2021
10:30
25-26/105 & online
We propose a generic construction of interpolation algorithms over the projective line for the multiplication in any finite extension of finite fields. This is a specialization of the method of interpolation on algebraic curves introduced by David and Gregory Chudnovsky. We will use generalizations of this method, in particular the evaluation at places of arbitrary degrees. Our algorithms correspond to usual techniques of polynomial interpolation in small extensions and are defined recursively as the degree of the extension increases. We show that their bilinear complexity is competitive and that they can be constructed in polynomial time.
I2M, Aix Marseille Université.
21 January 2022
11:00
Inria Saclay, room TBD & online
TBD
Mathematical Institute, University of Oxford.
22 November 2021
14:00
24-25/509 & online
In this talk, we present an efficient list decoding
algorithm for algebraic geometry (AG) codes. They are a
natural generalization of Reed-Solomon codes and include
some of the best codes in terms of robustness to
errors. The proposed decoder follows the Guruswami-Sudan
paradigm and is the fastest of its kind, generalizing
the decoder for one-point Hermitian codes by
J. Rosenkilde and P. Beelen to arbitrary AG codes. In
this fully general setting, our decoder achieves the
complexity $\widetilde{\mathcal{O}}(s
\ell^{\omega}\mu^{\omega - 1}(n+g))$, where $n$ is the
code length, $g$ is the genus, $\ell$ is the list size,
$s$ is the multiplicity and $\mu$ is the smallest
nonzero element of the Weierstrass semigroup at some
special place.
Joint work with J. Rosenkilde and P. Beelen.
Department of Applied Mathematics and Computer Science Mathematics, Danmarks Tekniske Universitet.
19 November 2021
11:00
25-26/105 & online
The Smith normal form of an $n \times n$
matrix $A $of integers or polynomials is a
diagonal matrix S$ = \operatorname{diag}(s_1, s_2, … , s_n)$
satisfying $s_1 | s_2 | .. | s_n$ with $A V
= U S$, where $U$ and $V$ are unimodular
matrices (i.e. $\det U = \det V = \pm 1$
(integers) or a constant (polynomials). The
$U$ and $V$ matrices represent row and column
operations converting $A$ into $S$.
In this talk we give a Las Vegas randomized
algorithm for computing $S, U, V$ in the
case where the matrix $A$ is a nonsingular
integer matrix. The expected running time of
our algorithm is about the same as the cost
required to multiply two matrices of the
same dimension and size of entries of
$A$. We also give explicit bounds on the
sizes of the entries of our unimodular
multipliers. The main tool used in our
construction is the so called Smith
massager, a relaxed version of our column
multiplier $V$.
This is joint work with Stavros Birmpilis and Arne Storjohann
Cheriton School of Computer Science, University of Waterloo.
15 October 2021
11:00
Inria Saclay, amphitheatre Sophie-Germain & online
Holonomic sequences are widely studied as
many objects interesting to mathematicians and
computer scientists are in this class. In the
univariate case, these are the sequences
satisfying linear recurrences with polynomial
coefficients and also referred to as P-finite
sequences. A subclass are C-finite sequences
satisfying a linear recurrence with constant
coefficients.
We'll see in this talk a natural extension
of this set of sequences:
which satisfy linear recurrence equations
with coefficients that are C-finite
sequences. We will show that C2-finite
sequences form a difference ring and provide
methods to compute in this ring.
LIX, École polytechnique.
24 September 2021
11:00
25-26/105 & online
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.
PolSys, LIP6, Sorbonne Université.