This talk presents necessary and sufficient conditions in terms of sign vectors for the injectivity of families of polynomials maps with arbitrary real exponents defined on the positive orthant. Our work relates and extends existing injectivity conditions expressed in terms of Jacobian matrices and determinants. In the context of chemical reaction networks with power-law kinetics, our results can be used to preclude as well as to guarantee multiple positive steady states. In the context of real algebraic geometry, our results reveal a partial multivariate generalization of the classical Descartes' rule of signs, for precluding multiple positive solutions.

This is joint work with Stefan Müller, Elisenda Feliu, Georg Regensburger, Carsten Conradi, and Alicia Dickenstein

We study the question when can a partial matrix be completed to a rank 1 probability matrix, i. e. a matrix with nonnegative entries which sum to 1. The motivation for studying the question comes from statistics: A lack of desired completion can provide a falsication test for partial observations to come from the independence model.

We first answer the question for diagonal partial matrices, then generalize it to block diagonal partial matrices and finally to arbitrary partial matrices. We show how to construct polynomial equations and inequalities that define the semialgebraic set of partial matrices which can be completed to rank 1 probability matrices. In case a partial matrix has a desired completion, we give an algorithm how to construct one, and if it has more than one such completion, we show how to construct a completion that minimizes the distance from a fixed probability distribution. We address the same questions also for diagonal partial tensors.

This talk is based on joint work with Zvi Rosen.

Exploiting a connection between amoebas and tropical curves we devise a method to compute tropical curves using numerical algebraic geometry, implement a heuristic algorithm, and apply this to several examples at the boundary of the capabilities of symbolic methods. (Joint work with Anders Jensen and Josephine Yu.)

Hilbert's Nullstellensatz is a cornerstone in Algebraic Geometry. It describes by a Bézout identity when  polynomial equations do not share any root in an algebraically closed field. Here I will present sharp results on the heights and degrees of polynomials showing up in the Bezout identity, when the polynomials defining field admits a height notion. And hopefully I will be able to comment on some applications of these results to complexity problems over finite fields.

Bertini_real is software for decomposing real algebraic sets in any number of variables. Using Bertini's homotopy continuation tracker as its main engine, Bertini_real uses random real linear projections to implicitly parametrize the targeted algebraic set. By finding the critical sets — the places where the set is singular with respect to the projections — and then connecting the computed points on them, we produce a decomposition in terms of cells, where the interior is a singularity-free region, and the boundaries are critical, singular, or an artificially imposed boundary capturing infinite behavior. Bertini_real currently will decompose sets of dimension 1 or 2; i.e. curves and surfaces. Bertini_real is a numerical method for performing decompositions, and offers improvements over existing algorithms in terms of the number of variables defining the variety, as well as allowing tracking on and decomposition of singular components. The cellular decomposition is readily refined, visualized, and 3D printed.

A non-zero polynomial of degree d has at most d complex roots. Moreover, Descartes proved that the number of real roots can be also bounded by a function on the number of monomials. A polynomial with t monomials has at most 2t-1 real roots.

What happens if we consider the solutions of a system of polynomials? In the complex case, Bézout's Theorem bounds the number of solutions by the product of the degrees. Is there, in the real case, a similar bound which only depends on the number of monomials? Khovanskií proved that this bound exists, but the given bound is exponential. Is it the optimal bound? This is an open question.

A particular case, known as Sevostyanov's problem, is the case of a system of one degree d polynomial and of one t-sparse polynomial. We will present in this talk a polynomial bound with respect to t and d for this problem. It is a joint work with Pascal Koiran and Natacha Portier.

Let G be a bounded open subset of Euclidean space with real algebraic boundary. In a first part of the talk we consider the case where $G={x: g(x) <=1}$ for some quasi-homogeneous polynomial "g" and derive several properties of "G" as well as the non-Gaussian integral \int exp(-g)dx. In particular we show that the volume of G is a convex function of the coefficients of "g" and solve a generalized version of the Lowner-John problem.

Next, we consider a more general case and under the assumptions that the degree "d" of the algebraic boundary is known and the power moments of the Lebesgue measure on G are known up to order 3d, we describe an algorithmic procedure for obtaining a polynomial vanishing on the boundary. The particular case of semi-algebraic sets defined by a single polynomial inequality raises an intriguing question related to the finite determinateness of the full moment sequence. Our approach relies on Stokes theorem and simple Hankel-type matrix identities.

In the sum of squares problem, we want to express the polynomial (x_1^2+…+x_n^2)(y_1^2+…+y_n^2) as f_1^2+…+f_k^2, with f_i bilinear in x and y. k lies somewhere between n and n^2, and it is an open problem to prove a superlunar lower bound on k. A lower bound of n^{1+\eps} with \eps>0 would imply an exponential lower bound on arithmetic circuit complexity of the permanent, in the non-commutative setting. I will describe an approach to the sum of squares problem, based on families of anticommuting matrices. Essentially, one needs to show that it is impossible to have many pairwise anticommuting matrices with high rank. I will prove some partial results in this direction.

Polynomial systems are ubiquitous in Mathematics, Sciences and Engineerings, and Groebner basis theory is one of the most powerful tools for solving polynomial systems from practice. Buchberger (1965) gave the first algorithm for computing Groebner bases and introduced some simple criteria for detecting useless S-pairs. Faugere (2002) introduced signatures and rewritten rules to detect useless S-pairs, and his F5 algorithm is significantly much faster than Buchberger's algorithm. In the last ten years or so, there has been extensive effort trying to modify F5 in order to have simpler algorithms that work for arbitrary sequence of polynomials (not necessarily homogeneous) and have rigorous proofs for correctness and finite termination.

In this talk, we present a new framework that underlies an algorithmic foundation for computing Groebner bases for both ideals and the related syzygy modules (the latter is useful for computing free resolutions). We give a simple criterion for strong Groebner bases that contain Groebner bases for both ideals and syzygy modules. This criterion can detect all useless J-pairs (without performing any reduction) for any sequence of polynomials, thus yielding an efficient algorithm for computing Groebner bases. All the rewritten rules in the literature can now be easily explained by this criterion. This is a joint work with Frank Volny IV (National Security Agency) and Mingsheng Wang (Chinese Academy of Sciences).

The 17th of the problems proposed by Steve Smale for the 21st century is concerned with the complexity for computing an approximate solution of a given system of $n$ complex polynomials in $n$ unknowns. More specifically, the 17th problem asks for a deterministic algorithm for this task that runs in time polynomial, on the average, in the size $N$ of the input system.

In joint work with Felipe Cucker, we managed to perform a smoothed analysis (in the sense of Spielman and Teng) of a linear homotopy algorithm for this problem that uses a random starting system. The smoothed complexity is polynomial in the input size and the variance of the random perturbation of the input systems. The techniques developed for this allow to exhibit and analyze a deterministic algorithm for computing an approximate solution that has an average complexity $N^{\Oh(\log\log N)}$, which is nearly a solution to Smale's 17th problem.

The methodology appears to be quite general: for instance it leads to new algorithms for computing eigenvalues and eigenvectors of matrices that can be shown to run in smoothed polynomial time.