Sparsity, Randomness and Convexity in Applied Algebraic Geometry

Abstract

In this dissertation we study three problems in applied algebraic geometry. The first problem is to construct an algorithmically efficient approximation to the real part of the zero set of an exponential sum. We construct such a polyhedral approximation using techniques from tropical geometry. We prove precise distance bounds between our polyhedral approximation and the real part of the zero set. Our bounds depend on the number of terms of the exponential sum and the minimal distance between the exponents. Despite the computational hardness of the membership problem for the real part of the zero set, we prove that our polyhedral approximation can be computed by linear programing on the real BSS machine.

The second problem is to study the ratio of sums of squares polynomials inside the set of nonnegative polynomials. Our focus is on the effect of fixed monomial structure to the ratio of these two sets. We study this problem quantitatively by combining convex geometry and algebra. Some of our methods work for arbitrary Newton polytopes; however our main theorem is stated for multi-homogenous polynomials. Our main theorem provides quantitative versions of some known algebraic facts, and also refines earlier quantitative results.

The third problem is to study the condition number of polynomial systems ‘on average’. Condition number is a vital invariant of polynomial systems which controls their computational complexity. We analyze the condition number of random polynomial systems for a broad family of distributions. Our work shows that earlier results derived for the polynomial systems with real Gaussian independent random coefficients can be extended to the broader family of sub-Gaussian random variables allowing dependencies. Our results are near optimal for overdetermined systems but there is room for improvement in the case of square systems of random polynomials.

The main idea binding our three problems is to observe structure and randomness phenomenon in the space of polynomials. We used combinatorial algebraic geometry to observe the ‘structure’ and convex geometric analysis to understand the ‘randomness’. We believe results presented in this dissertation are just the first steps of the interaction between these two fields.