Combinatorial and algorithmic aspects of hyperbolic polynomials

Abstract

Let $p(x_1,...,x_n)={\sum }_{(r_1,...,r_n)\in I_{n,n}}{a}_{(r_1,...,r_n)}{\prod }_{1\le i\le n}{x}_i^{r_i}$ be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients. The support of such polynomial $p(x_1,...,x_n)$ is defined as $supp(p)=\{(r_1,...,r_n)\in I_{n,n}:a_{(r_1,...,r_n)}\ne 0\}$ . The convex hull $CO(supp(p))$ of $supp(p)$ is called the Newton polytope of $p$ . We study the following decision problems, which are far-reaching generalizations of the classical perfect matching problem : {itemize} {\bf Problem 1 .} Consider a homogeneous polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,..,1)\in supp(p)$ ?} {\bf Problem 2 .} Consider a homogeneous polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,..,1)\in CO(supp(p))$ ?} {itemize} We prove that for hyperbolic polynomials these two problems are equivalent and can be solved by deterministic polynomial-time oracle algorithms . This result is based on a "hyperbolic" generalization of Rado theorem .

28 pages, extended and edited version . A proof of Conjecture 2.11 (hyperbolic van der Waerden conjecture) will be posted shortly

Cited by in corpus (13)

• Polynomials with the half-plane property and matroid theory
• Obstructions to determinantal representability
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Generalized Friedland-Tverberg inequality: applications and extensions
• Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all
• Interior-point methods for unconstrained geometric programming and scaling problems
• Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications
• Hyperbolic polynomials and the Marcus-Spielman-Srivastava theorem
• Polynomial time algorithms in invariant theory for torus actions
• Barriers for recent methods in geodesic optimization
• Report on "Mathematical Aspects of P vs. NP and its Variants."