Under the auspices of the Computational Complexity Foundation (CCF)

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

TR13-141 | 8th October 2013
Leonid Gurvits

#### Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>>

ISSN 1433-8092 | Imprint