Leonid Gurvits

STOC Conference 2021 Conference Paper

Capacity lower bounds via productization

• Leonid Gurvits
• Jonathan Leake

We give a sharp lower bound on the capacity of a real stable polynomial, depending only on the value of its gradient at x = 1. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000, which was crucial to the analysis of their permanent approximation algorithm. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications, and in fact we use our bound to construct a new scaling algorithm for real stable polynomials. Our bound is also quite similar to one used very recently by Karlin-Klein-Oveis Gharan to give an improved approximation factor for metric TSP.

STOC Conference 2017 Conference Paper

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute: (1) Feasibility of BL-datum, (2) Optimal BL- constant, (3) Weak separation oracle for BL-polytopes. What is particularly exciting about this progress, beyond the better understanding of BL- inequalities, is that the objects above naturally encode rich families of optimization problems which had no prior efficient algorithms. In particular, the BL-constants (which we efficiently compute) are solutions to non-convex optimization problems, and the BL-polytopes (for which we provide efficient membership and separation oracles) are linear programs with exponentially many facets. Thus we hope that new combinatorial optimization problems can be solved via reductions to the ones above, and make modest initial steps in exploring this possibility. Our algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by [Gur04]. To obtain the results above, we utilize the two (very recent and different) algorithms for the operator scaling problem [GGOW16, IQS15a]. Our reduction implies algorithmic versions of many of the known structural results on BL-inequalities, and in some cases provide proofs that are different or simpler than existing ones. Further, the analytic properties of the [GGOW16] algorithm provide new, effective bounds on the magnitude and continuity of BL-constants, with applications to non-linear versions of BL-inequalities; prior work relied on compactness, and thus provided no bounds. On a higher level, our application of operator scaling algorithm to BL-inequalities further connects analysis and optimization with the diverse mathematical areas used so far to mo- tivate and solve the operator scaling problem, which include commutative invariant theory, non-commutative algebra, computational complexity and quantum information theory.

FOCS Conference 2017 Conference Paper

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

• Nima Anari
• Leonid Gurvits
• Shayan Oveis Gharan
• Amin Saberi

We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c = γ+1 ≃ 4: 84. We write a natural convex relaxation and show that its optimum solution gives a cn approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices. We also show that our result implies an approximate version of the permanent-ontop conjecture, which was recently refuted in its original form; we show that the permanent is within a cn factor of the top eigenvalue of the Schur power matrix.

FOCS Conference 2016 Conference Paper

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

• Ankit Garg 0001
• Leonid Gurvits
• Rafael Oliveira 0002
• Avi Wigderson

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutativealgebra.

I&C Journal 2015 Journal Article

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

• Leonid Gurvits

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorithmic 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 column sums within simply exponential multiplicative factor. This new algorithm is a particular instance of new polynomial time deterministic algorithms related to the multiple partial differentiation of polynomials given by evaluation oracles.

FOCS Conference 2014 Conference Paper

Bounds on the Permanent and Some Applications

• Leonid Gurvits
• Alex Samorodnitsky

We give new lower and upper bounds on the permanent of a doubly stochastic matrix. Combined with previous work, this improves on the deterministic approximation factor. We also give a combinatorial application of the lower bound, proving S. Friedland's "Asymptotic Lower Matching Conjecture"for the monomer-dimer problem.

MFCS Conference 2013 Conference Paper

A Note on Deterministic Poly-Time Algorithms for Partition Functions Associated with Boolean Matrices with Prescribed Row and Column Sums

• Leonid Gurvits

Abstract 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 column sums within simply exponential multiplicative factor. This new algorithm is a particular instance of new polynomial time deterministic algorithms related to the multiple partial differentiation of polynomials given by evaluation oracles.

STOC Conference 2006 Conference Paper

Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications

• Leonid Gurvits

Let p(x 1 ,...,x n ) = p(X), X ∈ R n be a homogeneous polynomial of degree n in n real variables, e = (1,1,.,1) ∈ R n be a vector of all ones . Such a polynomial p is called e-hyperbolic if for all real vectors X ∈ R n the univariate polynomial equation p(te - X) = 0 has all real roots λ 1 (X) ≥ ... ≥ λ n (X). The number of nonzero roots |i :λ i (X) ≠ 0 | is called Rank p (X). An e-hyperbolic polynomial p is called POS-hyperbolic if roots of vectors X ∈ 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 of this paper 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 ) ≥ ∏ 1 ≤ i ≤ n x i ; x i > 0, 1 ≤ i ≤ n, then the following inequality holds ∂ n /∂ x 1 ...∂ x n p(0,...,0) ≥ ∏ 1 ≤ i ≤ n (G i -1/G i ) G i -1 , where G i = min(R i , n+1-i) . This inequality 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 which are products of linear forms with nonnegative coefficients.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 x n entry-wise non-negative matrices within a multiplicative factor e n /n m for any fixed positive m; and a deterministic poly-time algorithm approximating the permanent of n x n matrix A having at most k nonzero entries in each column to within a multiplicative factor (k-1/k) (k-1)n .This paper introduces a new powerful "polynomial" technique, which allows us to simplify and unify hard and key known results as well as to prove new important theorems and get new algorithms.

MFCS Conference 2005 Conference Paper

On the Complexity of Mixed Discriminants and Related Problems

• Leonid Gurvits

Abstract We prove that it is # P -hard to compute the mixed discriminant of rank 2 positive semidefinite matrices. We present poly-time algorithms to approximate the ”beast”. We also prove NP-hardness of two problems related to mixed discriminants of rank 2 positive semidefinite matrices. One of them, the so called Full Rank Avoidance problem, had been conjectured to be NP-Complete in [23] and in [25]. We also present a deterministic poly-time algorithm computing the mixed discriminant D ( A 1, .. , A N ) provided that the linear (matrix) subspace generated by { A 1, .. , A N } is small and discuss randomized algorithms approximating mixed discriminants within absolute error.

STOC Conference 2003 Conference Paper

Classical deterministic complexity of Edmonds' Problem and quantum entanglement

• Leonid Gurvits

Generalizing a decision problem for bipartite perfect matching, J. Edmonds introduced in [14] the problem (now known as the Edmonds Problem) of deciding if a given linear subspace of M(N) contains a nonsingular matrix, where M(N) stands for the linear space of complex N x N matrices. This problem led to many fundamental developments in matroid theory etc.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 nonnegative entries. (Here operator refers to maps from matrices to matrices.) First, we reformulate the Edmonds Problem in terms of of completely positive operators, or equivalently, in terms of bipartite density matrices. It turns out that one of the most important cases when Edmonds' problem can be solved in polynomial deterministic time, i.e. an intersection of two geometric matroids, corresponds to unentangled (aka separable) bipartite density matrices. We introduce a very general class (or promise) of linear subspaces of M(N) on which there exists a polynomial deterministic time algorithm to solve Edmonds' problem. The algorithm is a thoroughgoing generalization of algorithms in [23], [26], and its analysis benefits from an operator analog of permanents, so called Quantum Permanents. Finally, we prove that the weak membership problem for the convex set of separable normalized bipartite density matrices is NP-HARD.

TCS Journal 2001 Journal Article

A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces

• Leonid Gurvits

We show that “B is of type p>1” is a necessary and sufficient condition for a learnability of a class of linear bounded functionals with norm ⩽1 restricted to the unit ball in Banach space B. On the way, we give very short probabilistic proof for Vapnik's result (Hilbert space and improved) and improve our result with Pascal Koiran for convex halls of indicator functions. The approach we use in this paper allows to connect various results about learnability and approximation.

STOC Conference 2000 Conference Paper

A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume

• Leonid Gurvits
• Alex Samorodnitsky

IROS Conference 1994 Conference Paper

Mobile robot localization using landmarks

• Margrit Betke
• Leonid Gurvits

We describe an efficient algorithm for localizing a mobile robot in an environment with landmarks. We assume that the robot has a camera and maybe other sensors that enable it to both identify landmarks and measure the angles subtended by these landmarks. We show how to estimate the robot's position using a new technique that involves a complex number representation of the landmarks. Our algorithm runs in time linear in the number of landmarks. We present results of our simulations and propose how to use our method for robot navigation. >

ICRA Conference 1992 Conference Paper

Attitude control of space platform/manipulator system using internal motion

• Chris Fernandes
• Leonid Gurvits
• Zexiang Li 0001

The authors formulate the dynamic equations of a system consisting of a 3-degree-of-freedom Puma-like manipulator attached to a space platform (e. g. a space station or a satellite) as an NMP (nonholonomic motion planning) problem and discuss controllability of the system. They describe the application of a simple algorithm for obtaining approximate optimal solutions. They conclude with results of a simulation experiment. >

ICRA Conference 1992 Conference Paper

Averaging approach to nonholonomic motion planning

• Leonid Gurvits

The author considers the problem of motion planning for a nonholonomic system with drift. Open-loop and feedback solutions for nonholonomic motion planning (NMP) are constructed by using the averaging technique that is well known in applied mathematics. An algorithm for open-loop and feedback solutions of NMP is introduced. The main step in the algorithm is the case of first order Lie brackets. This case, as is shown, is equivalent to NMP for Brockett's system considered over functional commutative algebra. Feedback solutions are constructed in the same manner. From a robotics point of view, it is shown that NMP can be reduced to the holonomic problem. As linear algebra plays a crucial role in linear control theory, polylinear algebra is crucial for NMP. The rolling disk example is used to illustrate the feedback algorithm. >

ICRA Conference 1991 Conference Paper

A variational approach to optimal nonholonomic motion planning

• Chris Fernandes
• Leonid Gurvits
• Zexiang Li 0001

Nonholonomic motion planning (NMP) problems arise not only from the classical nonholonomic constraints, but also from symmetries and conservation laws of holonomic systems. In NMP problems an admissible configuration space path is constrained to a given nonholonomic distribution. Thus, NMP deals with the problem of (optimal) path finding subject to a nonholonomic distribution and possibly to additional holonomic constraints. The authors first study several representative NM systems and formulate the NMP problem. Variational principles are used to characterize optimal solutions to these problems. A simple algorithm solving an NMP problem is proposed, and simulation results are presented. >