ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > CONVEX:
Reports tagged with convex:
TR04-070 | 22nd June 2004
Leonid Gurvits

Combinatorial and algorithmic aspects of hyperbolic polynomials

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 ... more >>>


TR06-025 | 19th January 2006
Leonid Gurvits

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\ Sharper Bounds , Simpler Proofs and Algorithmic Applications

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 ... more >>>




ISSN 1433-8092 | Imprint