Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables ,
$e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is
called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial
equation $p(te - X) = 0$ has all real roots $\lambda_{1}(X) \geq ... \geq \lambda_{n}(X)$ .
The number of nonzero roots $|\{i :\lambda_{i}(X) \neq 0 \}|$ is called $Rank_{p}(X)$ .
A $e$-hyperbolic polynomial $p$ is called $POS$-hyperbolic if roots
of vectors $X \in R^{n}_{+}$ with nonnegative coordinates are also nonnegative
(the orthant $R^{n}_{+}$ belongs to the hyperbolic cone) and $p(e) > 0$ .
Below $\{e_1,...,e_n\}$ stands for the canonical orthogonal basis in $R^{n}$. \\
The main results states that if $p(x_1,x_2,...,x_n)$ is a $POS$-hyperbolic (homogeneous) polynomial of degree $n$ ,
$Rank_{p} (e_{i}) = R_i$ and
$
p(x_1,x_2,...,x_n) \geq \prod_{1 \leq i \leq n} x_i ; x_i > 0 , 1 \leq i \leq n ,
$ \\
then the following inequality holds
$$
\frac{\partial^n}{\partial x_1...\partial x_n} p(0,...,0) \geq \prod_{1 \leq i \leq n} (\frac{G_{i} -1}{G_{i}})^{G_{i} -1} (G_i = \min(R_{i} , n+1-i)) .
$$
This theorem is a vast (and unifying) generalization of the van der Waerden conjecture on the permanents of doubly stochastic matrices as well as
the Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs .
These two famous results correspond to the $POS$-hyperbolic polynomials being
products of linear forms.
Section 2.2 provides the extension of the main result to
so called AF-polynomials , the class which is larger than
the class of $POS$-hyperbolic polynomial and includes volume
polynomials $Vol(x_1 C_1 +...+x_n C_n)$ , where $C_i , 1 \leq i \leq n$
are convex compact subsets of R^n . This extension leads
to a randomized poly-time algorithm to approximate the
mixed volume of $n$ convex compact subsets of R^n within multiplicative
factor $e^n$ .
Our proof is relatively simple and "noncomputational" ; it actually slightly improves Schrijver's lower bound ,
and uses very basic ( more or less centered around
Rolle's theorem ) properties of hyperbolic polynomials . \\
We present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating
the permanent of $n \times n$ nonnegative entry-wise matrices within a multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$ .
This paper introduces a new powerful "polynomial" technique , which allows as to simplify/unify famous and hard known results
as well to prove new important theorems .
The paper is (almost) entirely self-contained , most of the proofs can be found in the {\bf Appendices}.
