5 papers
A complexity analysis of the F4 Gröbner basis algorithm with tracer data
Robin Kouba, Vincent Neiger, Mohab Safey El Din
We provide a new complexity bound for the computation of grevlex Gröbner bases in the generic zero-dimensional case, relying on Moreno-SocÃas' conjecture. We first formalize a pr…
Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
Sara Khichane, Vincent Neiger
The fastest known algorithms for dealing with structured matrices, in the sense of the displacement rank measure, are randomized. For handling classical displacement structures, th…
Computing submatrices of the Hermite normal form of a structured polynomial matrix
Jérémy Berthomieu, Vincent Neiger, Hugo Passe
Following several decades of successive algorithmic improvements, works from the 2010s have showed how to compute the Hermite normal form (HNF) of a univariate polynomial matrix wi…
Faster modular composition using two relation matrices
Vincent Neiger, Bruno Salvy, Ãric Schost +1
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem…
Faster List Decoding of AG Codes
Peter Beelen, Vincent Neiger
In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in $…