93 citations · 154 across the 14 of their papers we have counts for
19 papers
Computing Isomorphisms between Products of Supersingular Elliptic Curves
Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer
The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for…
Dimension Results for Extremal-Generic Polynomial Systems over Complete Toric Varieties
Matías Bender, Pierre-Jean Spaenlehauer
We study polynomial systems with prescribed monomial supports in the Cox rings of toric varieties built from complete polyhedral fans. We present combinatorial formulas for the dim…
Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields
Antoine Leudière, Pierre-Jean Spaenlehauer
We explore algorithmic aspects of a simply transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian o…
Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
Aude Le Gluher, Pierre-Jean Spaenlehauer, Emmanuel Thomé
The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted and called $ξ(…
A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
Aude Le Gluher, Pierre-Jean Spaenlehauer
We propose a probabilistic variant of Brill-Noether's algorithm for computing a basis of the Riemann-Roch space associated to a divisor on a projective nodal plane curve…
Counting points on genus-3 hyperelliptic curves with explicit real multiplication
Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer
We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperelliptic curve defined over a finite field , with explicit real multiplic…
A Polyhedral Method for Sparse Systems with many Positive Solutions
Frédéric Bihan, Francisco Santos, Pierre-Jean Spaenlehauer
We investigate a version of Viro's method for constructing polynomial systems with many positive solutions, based on regular triangulations of the Newton polytope of the system. Th…
Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer
We present a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus defined over . It is based on the approache…
Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems
Jean-Charles Faugere, Pierre-Jean Spaenlehauer, Jules Svartz
B{é}zout 's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2 n solutions over algebraically closed fields. When only a small su…
Critical Point Computations on Smooth Varieties: Degree and Complexity bounds
Mohab Safey El Din, Pierre-Jean Spaenlehauer
Let V C n be an equidimensional algebraic set and g be an n-variate polynomial with rational coefficients. Computing the critical points of the map that evaluates g at th…
Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes
Frédéric Bihan, Pierre-Jean Spaenlehauer
Consider a regular triangulation of the convex-hull of a set of points in , and a real matrix of size . A version of Viro's method…
Sparse Gröbner Bases: the Unmixed Case
Jean-Charles Faugere, Pierre-Jean Spaenlehauer, Jules Svartz
Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amou…
A Quadratically Convergent Algorithm for Structured Low-Rank Approximation
Éric Schost, Pierre-Jean Spaenlehauer
Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix , the goal is to com…
Exact Solutions in Structured Low-Rank Approximation
Giorgio Ottaviani, Pierre-Jean Spaenlehauer, Bernd Sturmfels
Structured low-rank approximation is the problem of minimizing a weighted Frobenius distance to a given matrix among all matrices of fixed rank in a linear space of matrices. We st…
On the Complexity of Computing Critical Points with Gröbner Bases
Pierre-Jean Spaenlehauer
Computing the critical points of a polynomial function restricted to the vanishing locus of polynomials $f_1,\ldots, f_p\in\ma…
Critical Points and Gröbner Bases: the Unmixed Case
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a…
On the Complexity of Solving Quadratic Boolean Systems
Magali Bardet, Jean-Charles Faugère, Bruno Salvy +1
A fundamental problem in computer science is to find all the common zeroes of quadratic polynomials in unknowns over . The cryptanalysis of several modern cip…
On the Complexity of the Generalized MinRank Problem
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We study the complexity of solving the \emph{generalized MinRank problem}, i.e. computing the set of points where the evaluation of a polynomial matrix has rank at most . A natu…
Gröbner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these…