activity
20072025
most citedOn the Complexity of Solving Quadratic Boolean Systems

93 citations · 387 across the 28 of their papers we have counts for

collaborators

31 papers

quant-ph2025

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…

cs.SC2021

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…

math.AC2021

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…

cs.SC2020

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…

cs.SC2019

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…

cs.SC2018

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…

cs.SC2018

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…

cs.SC2018★ 14 cited

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…

cs.SC2018★ 5 cited

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…

cs.CR2017★ 22 cited

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…

cs.SC2017

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…

cs.SC2016★ 1 cited

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…

cs.SC2016★ 6 cited

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…

cs.SC2016

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…

math.AG2015★ 56 cited

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…

cs.SC2014★ 13 cited

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…

cs.IT2014

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…

math.AC2014★ 11 cited

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…

cs.SC2014★ 19 cited

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…

cs.SC2013★ 19 cited

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…

cs.SC2013★ 11 cited

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…

cs.SC2013★ 64 cited

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…

cs.SC2013★ 20 cited

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…

cs.SC2013★ 2 cited

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…