93 citations · 387 across the 28 of their papers we have counts for
31 papers
Quantum Key Distribution with Efficient Post-Quantum Cryptography-Secured Trusted Node on a Quantum Network
Yoann Piétri, Pierre-Enguerrand Verdier, Baptiste Lacour +13
Quantum Key Distribution (QKD) enables two distant users to exchange a secret key with information-theoretic security, based on the fundamental laws of quantum physics. While it is…
Polynomial-Division-Based Algorithms for Computing Linear Recurrence Relations
Jérémy Berthomieu, Jean-Charles Faugère
Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear re…
Koszul-type determinantal formulas for families of mixed multilinear systems
Matías R. Bender, Jean-Charles Faugère, Angelos Mantzaflaris +1
Effective computation of resultants is a central problem in elimination theory and polynomial system solving. Commonly, we compute the resultant as a quotient of determinants of ma…
Computing critical points for invariant algebraic systems
Jean-Charles Faugère, George Labahn, Mohab Safey El Din +2
Let be a field and , in be multivariate polynomials (with ) invariant under the action of $\m…
Gr{ö}bner Basis over Semigroup Algebras: Algorithms and Applications for Sparse Polynomial Systems
Matías Bender, Jean-Charles Faugère, Elias Tsigaridas
Gr{ö}bner bases is one the most powerful tools in algorithmic non-linear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential i…
A nearly optimal algorithm to decompose binary forms
Matías Bender, Jean-Charles Faugère, Ludovic Perret +1
Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. I…
In-depth comparison of the Berlekamp--Massey--Sakata and the Scalar-FGLM algorithms: the adaptive variants
Jérémy Berthomieu, Jean-Charles Faugère
The Berlekamp--Massey--Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence.Whenever quering a single…
Towards Mixed Gr{ö}bner Basis Algorithms: the Multihomogeneous and Sparse Case
Matías Bender, Jean-Charles Faugère, Elias Tsigaridas
One of the biggest open problems in computational algebra is the design of efficient algorithms for Gr{ö}bner basis computations that take into account the sparsity of the input po…
Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors
Matías Bender, Jean-Charles Faugère, Angelos Mantzaflaris +1
A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix. whos…
Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
Jean-Charles Faug`ere, Kelsey Horan, Delaram Kahrobaei +3
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algo…
In-depth comparison of the Berlekamp -- Massey -- Sakata and the Scalar-FGLM algorithms: the non adaptive variants
Jérémy Berthomieu, Jean-Charles Faugère
We compare thoroughly the Berlekamp -- Massey -- Sakata algorithm and the Scalar-FGLM algorithm, which compute both the ideal of relations of a multi-dimensional linear recurrent s…
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…
Determinantal sets, singularities and application to optimal control in medical imagery
Bernard Bonnard, Jean-Charles Faugère, Alain Jacquemard +2
Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast b…
GBLA -- Gröbner Basis Linear Algebra Package
Brice Boyer, Christian Eder, Jean-Charles Faugère +2
This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea of Faugère and Lachartre (GB reduction). We further exploit underlying struc…
Moment Varieties of Gaussian Mixtures
Carlos Améndola, Jean-Charles Faugère, Bernd Sturmfels
The points of a moment variety are the vectors of all moments up to some order of a family of probability distributions. We study this variety for mixtures of Gaussians. Following…
On the complexity of computing Gröbner bases for weighted homogeneous systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a…
Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups
Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret +2
The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alter…
A survey on signature-based Gröbner basis computations
Christian Eder, Jean-Charles Faugère
This paper is a survey on the area of signature-based Gröbner basis algorithms that was initiated by Faugère's F5 algorithm in 2002. We explain the general ideas behind the usage o…
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…
On the Complexity of the F5 Gröbner basis Algorithm
Magali Bardet, Jean-Charles Faugère, Bruno Salvy
We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We…
Polynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case
Jérémy Berthomieu, Jean-Charles Faugère, Ludovic Perret
Let and be two sets of nonlinear polynomials over ( being a fie…
Sparse FGLM algorithms
Jean-Charles Faugère, Chenqi Mou
Given a zero-dimensional ideal I in K[x1,...,xn] of degree D, the transformation of the ordering of its Groebner basis from DRL to LEX is a key step in polynomial system solving an…
Polynomial Systems Solving by Fast Linear Algebra
Jean-Charles Faugère, Pierrick Gaudry, Louise Huot +1
Polynomial system solving is a classical problem in mathematics with a wide range of applications. This makes its complexity a fundamental problem in computer science. Depending on…
On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Let $\K$ be a field and $(f_1, \ldots, f_n)\subset \K[X_1, \ldots, X_n]$ be a sequence of quasi-homogeneous polynomials of respective weighted degrees w.r.t a…