Leonid Gurvits

STOC Conference 2021 Conference Paper

Capacity lower bounds via productization

• Leonid Gurvits
• Jonathan Leake

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.

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

TCS Journal 2001 Journal Article

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

• Leonid Gurvits

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