Let V ⊂ Cn 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 the points of V is a cornerstone of several algorithms in real algebraic geometry and optimization. Under the assumption that the critical locus is finite and that the projective closure of V is smooth, we provide sharp upper bounds on the degree of the critical locus which depend only on deg(g) and the degrees of the generic polar varieties associated to V. Hence, in some special cases where the degrees of the generic polar varieties do not reach the worst-case bounds, this implies that the number of critical points of the evaluation map of g is less than the currently known degree bounds. We show that, given a lifting fiber of V, a slight variant of an algorithm due to Bank, Giusti, Heintz, Lecerf, Matera and Solerno computes these critical points in time which is quadratic in this bound up to logarithmic factors, linear in the complexity of evaluating the input system and polynomial in the number of variables and the maximum degree of the input polynomials.

Bezout's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2n solutions over algebraically closed fields. When only a small subset M of monomials appear in the equations (fewnomial systems), the number of solutions may decrease dramatically. We focus in this work on subsets of quadratic monomials M such that generic systems with support M do not admit any solution at all. For these systems, Hilbert's Nullstellensatz ensures the existence of algebraic certificates of inconsistency. However, up to our knowledge all known bounds on the sizes of such certificates ---including those which take into account the Newton polytopes of the polynomials--- are exponential in n. Our main results show that if the inequality 2|M|-2n ≤ √{1+8ν}-1 holds for a quadratic fewnomial system -- where ν is the matching number of a graph associated with M, and |M| is the cardinality of M -- then there exists generically a certificate of inconsistency of linear size (measured as the number of coefficients in the ground field K). Moreover this certificate can be computed within a polynomial number of arithmetic operations. Next, we evaluate how often this inequality holds, and we give evidence that the probability that the inequality is satisfied depends strongly on the number of squares. More precisely, we show that if M is picked uniformly at random among the subsets of n+k+1 quadratic monomials containing at least Ω(n1/2+ε) squares, then the probability that the inequality holds tends to 1 as n grows. Interestingly, this phenomenon is related with the matching number of random graphs in the Erdos-Renyi model. Finally, we provide experimental results showing that certificates in inconsistency can be computed for systems with more than 10000 variables and equations.

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 amounts to computing in a semigroup algebra, i.e. an algebra generated by a subset of Laurent monomials. In order to solve symbolically sparse systems, we introduce sparse Gröbner bases, an analog of classical Gröbner bases for semigroup algebras, and we propose sparse variants of the F5 and FGLM algorithms to compute them. Our prototype "proof-of-concept" implementation shows large speedups (more than 100 for some examples) compared to optimized (classical) Gröbner bases software. Moreover, in the case where the generating subset of monomials corresponds to the points with integer coordinates in a normal lattice polytope P ⊂ Rn and under regularity assumptions, we prove complexity bounds which depend on the combinatorial properties of P. These bounds yield new estimates on the complexity of solving 0-dim systems where all polynomials share the same Newton polytope (unmixed case). For instance, we generalize the bound min(n1, n2) + 1 on the maximal degree in a Gröbner basis of a 0-dim. bilinear system with blocks of variables of sizes (n1, n2) to the multilinear case: Σ ni - max(ni) + 1. We also propose a variant of Fröberg's conjecture which allows us to estimate the complexity of solving overdetermined sparse systems. Finally, our complexity results apply in the dense (usual) case and, as a surprising by-product, we prove that restrictive assumptions in usual complexity estimates of classical inhomogeneous Gröbner bases algorithms can be removed.

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 map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...).

Computing loci of rank defects of linear matrices (also called the MinRank problem) is a fundamental NP-hard problem of linear algebra which has applications in Cryptology, in Error Correcting Codes and in Geometry. Given a square linear matrix (i.e. a matrix whose entries are k-variate linear forms) of size n and an integer r, the problem is to find points such that the evaluation of the matrix has rank less than r+1. The aim of the paper is to obtain the most efficient algorithm to solve this problem. To this end, we give the theoretical and practical complexity of computing Gröbner bases of two algebraic formulations of the MinRank problem. Both modelings lead to structured algebraic systems. The first modeling, proposed by Kipnis and Shamir generates bihomogeneous equations of bi-degree (1,1). The second one is classically obtained by the vanishing of the (r+1)-minors of the given