Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-070 | 22nd June 2004 00:00

Combinatorial and algorithmic aspects of hyperbolic polynomials

RSS-Feed




TR04-070
Authors: Leonid Gurvits
Publication: 16th August 2004 17:08
Downloads: 3036
Keywords: 


Abstract:

Let p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq 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)} \neq 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 :
\begin{itemize}
\item
{\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) ? }
\item
{\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)) ? }
\end{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 .



ISSN 1433-8092 | Imprint