An upper bound on the ergodic capacity of {\bf MIMO} channels was introduced recently in arXiv:0903.1952. This upper bound amounts to the maximization on the simplex of some multilinear polynomial...
Michael J. Donahue, Leonid Gurvits, Christian Darken, Eduardo Sontag
This paper deals with sparse approximations by means of convex combinations of elements from a predetermined “basis ” subset S of a function space. Specifically, the focus is on the rate at which...
On multivariate Newton(like) inequalities (2008)
We study multivariate entire functions and polynomials with non-negative coefficients. A class of {\bf Strongly Log-Concave} entire functions, generalizing {\it Minkowski} volume polynomials, is...
R. Pemantle conjectured, and T.M. Liggett proved in 1997, that the convolution of two ultra-logconcave is ultra-logconcave. Liggett's proof is elementary but long. We present here a short proof,...
Michael J. Donahue, Leonid Gurvits, Christian Darken, Eduardo Sontag
This paper deals with sparse approximations by means of convex combinations of elements from a predetermined “basis ” subset S of a function space. Specifically, the focus is on the rate at which...
Definite integration and summation are P-hard (2007)
Leonid Gurvits, Warren D. Smith
We show that the common symbolic manipulation tasks of computing multiple partial derivatives, definite integration, and definite summation, are #P-hard, i.e., at least as hard as counting the...
Let $p$ be a homogeneous polynomial of degree $n$ in $n$ variables, $p(z_1,...,z_n) = p(Z)$, $Z \in C^{n}$. We call such a polynomial $p$ {\bf H-Stable} if $p(z_1,...,z_n) \neq 0$ provided the real...
Static Allocation of Multirail Networks (2007)
Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits
Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault-tolerance of current high-performance clusters. This report...
We study various stabilities and controllabilities of linear switched systems, including those appearing in the quantum computations context. A number of new results and connections is presented,...
Let ${\bf K} = (K_1, ..., K_n)$ be an $n$-tuple of convex compact subsets in the Euclidean space $\R^n$, and let $V(\cdot)$ be the Euclidean volume in $\R^n$. The Minkowski polynomial $V_{{\bf K}}$...
Dual-frequency VSOP Imaging of a High-redshift Radio Quasar PKS 1402+044 (2006)
Yang, Jun, Gurvits, Leonid, Lobanov, Andrei, Frey, Sandor, Hong, Xiao-Yu
Based on the VLBI Space Observatory Programme (VSOP) observations at 1.6 and 5 GHz, we find that the luminous high-redshift (z=3.215) quasar PKS 1402+044 (J1405+0415) has a pronounced 'core--jet'...
Generalized Friedland-Tverberg inequality: applications and extensions (2006)
Friedland, Shmuel, Gurvits, Leonid
We derive here the Friedland-Tverberg inequality for positive hyperbolic polynomials. This inequality is applied to give lower bounds for the number of matchings in $r$-regular bipartite graphs. It...
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...
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}...
Better bound on the exponent of the radius of the multipartite separable ball (2004)
Gurvits, Leonid, Barnum, Howard
We show that for an m-qubit quantum system, there is a ball of radius asymptotically approaching kappa 2^{-gamma m} in Frobenius norm, centered at the identity matrix, of separable (unentangled)...
On Matrix Polynomials with Real Roots (2004)
Gurvits, Leonid, Rodman, Leiba
It is proved that the roots of combinations of matrix polynomials with real roots can be recast as eigenvalues of combinations of real symmetric matrices, under certain hypotheses. The proof is based...
Van der Waerden Conjecture for Mixed Discriminants (2004)
We prove that the mixed discriminant of doubly stochastic $n$-tuples of semidefinite hermitian $n \times n$ matrices is bounded below by $\frac{n!}{n^{n}}$ and that this bound is uniquely attained at...
Combinatorial and algorithmic aspects of hyperbolic polynomials (2004)
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...
Combinatorics hidden in hyperbolic polynomials and related topics (2004)
The main topic of this paper is various "hyperbolic" generalizations of the Edmonds-Rado theorem on the rank of intersection of two matroids. We prove several results in this direction and pose a few...
Classical deterministic complexity of Edmonds' problem and Quantum Entanglement (2003)
This paper continues research initiated in quant-ph/0201022 . The main subject here is the so-called Edmonds' problem of deciding if a given linear subspace of square matrices contains a nonsingular...
Separable balls around the maximally mixed multipartite quantum states (2003)
Gurvits, Leonid, Barnum, Howard
We show that for an m-partite quantum system, there is a ball of radius 2^{-(m/2-1)} in Frobenius norm, centered at the identity matrix, of separable (unentangled) positive semidefinite matrices....
Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. (2002)
Chistov, Alexander, Fournier, Hervé, Gurvits, Leonid, Koiran, Pascal
(eng) Let E be a vector space of dimension n over an infinite field K. We give polynomial time constructions of families of r-dimensional subspaces of E with the following transversality property:...
Largest separable balls around the maximally mixed bipartite quantum state (2002)
Gurvits, Leonid, Barnum, Howard
For finite-dimensional bipartite quantum systems, we find the exact size of the largest balls, in spectral $l_p$ norms for $1 \le p \le \infty$, of separable (unentangled) matrices around the...
Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with...
Vandermonde Matrices, NP-Completeness, (2002)
École Normale, Supérieure Lyon, Er Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran, ...
Let K be an infinite field. We give polynomial time constructions of families of r-dimensional subspaces of K n with the following transversality property: any linear subspace of K n of dimension n...
Using multirail networks in high-performance clusters (2001)
Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits
Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault tolerance of current high-performance parallel computers. In...
Using multirail networks in high-performance clusters (2001)
Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits
Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault tolerance of current highperformance clusters. We present an...
Using multirail networks in high-performance clusters (2001)
Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits
Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault-tolerance of current high-performance clusters. We present and...
Using multirail networks in high-performance clusters (2001)
Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits
Using multiple independent networks (also known as rails) is an emerging technique to overcome bandwidth limitations and enhance fault tolerance of current high-performance parallel computers. In...
Leonid Gurvits, Peter N. Yianilos
) August 13, 1998 Abstract The deflation-inflation convex optimization method is introduced. One result is a simple and practical approximation algorithm for the max cut problem based on the...
Definite integration and summation are #P-hard (1998)
Leonid Gurvits, Warren D. Smith
Abstract — We show that the common symbolic manipulation tasks of computing multiple partial derivatives, definite integration, and definite summation, are #P-hard, i.e., at least as hard as...
Convergence Of Polynomially Bounded Semigroups Of Matrices (1997)
. It is proved that for polynomially bounded sets of matrices the notions of pointwise convergence and uniform convergence coincide. This result is also proved for certain sets of nonlinear maps on...
Constructive Approximation (1997)
Springer-Verlag Newyork, Michael J. Donahue, Leonid Gurvits, Christian Darken, Eduardo Sontag
. This paper deals with sparse approximations by means of convex combinations of elements from a predetermined "basis" subset S of a function space. Specifically, the focus is on the rate...
A note on VC-dimension and measure of sets of reals (1995)
Shai Ben-david, Leonid Gurvits
Vapnik and Chervonenkis proposed in [VC71] a combinatorial notion of dimension that reflects the `combinatorial complexity ' of families of sets. In the two decades that have passed since that...
Relating Egomotion and Image Evolution (1995)
Barak A. Pearlmutter, Leonid Gurvits
By considering the dynamics of the apparent motion of a stationary object relative to a moving observer, we construct a partial differential equation that relates the changes in an image to the...
Mobile Robot Localization using Landmarks (1995)
We describe an efficient method for localizing a mobile robot in an environment with landmarks. We assume that the robot can identify these landmarks and measure their bearings relative to each...
Rates of Convex Approximation in Non-Hilbert Spaces (1994)
Michael J. Donahue, Leonid Gurvits, Christian Darken, Eduardo Sontag
. This paper deals with sparse approximations by means of convex combinations of elements from a predetermined "basis" subset S of a function space. Specifically, the focus is on the rate...