All reports by Author Leonid Gurvits:

__
TR23-190
| 15th November 2023
__

Leonid Gurvits, Nathan Klein, Jonathan Leake#### From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Revisions: 1

__
TR20-110
| 22nd July 2020
__

Leonid Gurvits, Jonathan Leake#### Capacity Lower Bounds via Productization

Revisions: 2

__
TR13-141
| 8th October 2013
__

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

Revisions: 1

__
TR11-169
| 14th December 2011
__

Leonid Gurvits#### Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

Revisions: 2

__
TR07-037
| 2nd February 2007
__

Leonid Gurvits#### Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Revisions: 1

__
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

__
TR05-103
| 17th August 2005
__

Leonid Gurvits#### A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

__
TR04-070
| 22nd June 2004
__

Leonid Gurvits#### Combinatorial and algorithmic aspects of hyperbolic polynomials

Leonid Gurvits, Nathan Klein, Jonathan Leake

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of ... more >>>

Leonid Gurvits, Jonathan Leake

The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities ... more >>>

Leonid Gurvits

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

Leonid Gurvits

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality

\begin{equation} \label{le}

per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n

\end{equation}

We prove in this paper the following generalization (or just clever ...
more >>>

Leonid Gurvits

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.

Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and

with better rates if the affine dimensions of most of the sets $K_i$ are small.\\

Our approach is ...
more >>>

Leonid Gurvits

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

Leonid Gurvits

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .

Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... more >>>

Leonid Gurvits

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