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
Showing cs.SCShow all

23 papers · 1 filter

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…

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.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…

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.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…

cs.SC2012

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…

cs.SC2011★ 93 cited

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…

cs.SC2011★ 3 cited

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…

cs.SC2010★ 6 cited

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…

cs.SC2009★ 13 cited

Computing modular correspondences for abelian varieties

Jean-Charles Faugère, David Lubicz, Damien Robert

The aim of this paper is to give a higher dimensional equivalent of the classical modular polynomials . If is the -invariant associated to an elliptic curve $E_…