Leonid Gurvits

According to our database, Leonid Gurvits authored at least 52 papers between 1991 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.

Leonid Gurvits, Nathan Klein, Jonathan Leake

Electron. Colloquium Comput. Complex., 2023

2021

Counting matchings via capacity-preserving operators.

Leonid Gurvits, Jonathan Leake

Comb. Probab. Comput., 2021

2020

Operator Scaling: Theory and Applications.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Found. Comput. Math., 2020

Capacity Lower Bounds via Productization.

Leonid Gurvits, Jonathan Leake

Electron. Colloquium Comput. Complex., 2020

2019

Complexity of full counting statistics of free quantum particles in entangled states.

Dmitri A. Ivanov, Leonid Gurvits

CoRR, 2019

2017

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

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices.

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

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Algorithmic aspects of Brascamp-Lieb inequalities.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

CoRR, 2016

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

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2014

Bounds on the Permanent and Some Applications.

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

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

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2013

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

Leonid Gurvits

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012

The Social Will-Testing Game and its Solution

Leonid Gurvits, J. Stephen Judd

CoRR, 2012

2011

Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation.

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2011

Unharnessing the power of Schrijver's permanental inequality

Leonid Gurvits

CoRR, 2011

2009

On the NP-Hardness of Checking Matrix Polytope Stability and Continuous-Time Switching Stability.

Leonid Gurvits, Alexander Olshevsky

IEEE Trans. Autom. Control., 2009

A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor.

Leonid Gurvits

Discret. Comput. Geom., 2009

A proof of the log-concavity conjecture related to the computation of the ergodic capacity of MIMO channels

Leonid Gurvits

CoRR, 2009

A Short Proof, Based on Mixed Volumes, of Liggett's Theorem on the Convolution of Ultra-Logconcave Sequences.

Leonid Gurvits

Electron. J. Comb., 2009

2008

Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer-Dimer Entropy.

Shmuel Friedland, Leonid Gurvits

Comb. Probab. Comput., 2008

Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all.

Leonid Gurvits

Electron. J. Comb., 2008

2007

On the Stability of Switched Positive Linear Systems.

Leonid Gurvits, Robert Shorten, Oliver Mason

IEEE Trans. Autom. Control., 2007

Polynomial time algorithms to approximate mixed volumes within a simply exponential factor.

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2007

2006

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications.

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2006

2005

On Matrix Polynomials with Real Roots.

Leonid Gurvits, Leiba Rodman

SIAM J. Matrix Anal. Appl., 2005

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

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2005

On the Complexity of Mixed Discriminants and Related Problems.

Leonid Gurvits

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

A note on common quadratic Lyapunov functions for linear inclusions: Exact results and Open Problems.

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the 44th IEEE IEEE Conference on Decision and Control and 8th European Control Conference Control, 2005

2004

Classical complexity and quantum entanglement.

Leonid Gurvits

J. Comput. Syst. Sci., 2004

Combinatorial and algorithmic aspects of hyperbolic polynomials

Leonid Gurvits

Electron. Colloquium Comput. Complex., 2004

2003

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces.

Alexander L. Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran

Found. Comput. Math., 2003

Using multirail networks in high-performance clusters.

Salvador Coll, Eitan Frachtenberg, Fabrizio Petrini, Adolfy Hoisie, Leonid Gurvits

Concurr. Comput. Pract. Exp., 2003

Classical deterministic complexity of Edmonds' Problem and quantum entanglement.

Leonid Gurvits

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

What is the finiteness conjecture for linear continuous time inclusions?

Leonid Gurvits

Proceedings of the 42nd IEEE Conference on Decision and Control, 2003

2002

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary.

Leonid Gurvits, Alex Samorodnitsky

Discret. Comput. Geom., 2002

2001

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

Leonid Gurvits

Theor. Comput. Sci., 2001

2000

A Note On Vc-Dimension And Measure Of Sets Of Reals.

Shai Ben-David, Leonid Gurvits

Comb. Probab. Comput., 2000

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

Leonid Gurvits, Alex Samorodnitsky

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1997

Convergence of Polynomially Bounded Semigroups of Matrices.

Leonid Gurvits, Leiba Rodman

SIAM J. Matrix Anal. Appl., April, 1997

Mobile robot localization using landmarks.

Margrit Betke, Leonid Gurvits

IEEE Trans. Robotics Autom., 1997

Approximation and Learning of Convex Superpositions.

Leonid Gurvits, Pascal Koiran

J. Comput. Syst. Sci., 1997

Linear Algebraic Proofs of VC-Dimension Based Inequalities.

Leonid Gurvits

Proceedings of the Computational Learning Theory, Third European Conference, 1997

1995

A Further Note on Max-Min Properties of Matrix Factor Norms.

Leonid Gurvits, Anne Greenbaum

SIAM J. Sci. Comput., 1995

A Note on VC-Dimension and Measures of Sets of Reals.

Shai Ben-David, Leonid Gurvits

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

An Upper Bound for the Real Part of Nonmaximal Eigenvalues of Nonnegative Irreducible Matrices.

Shmuel Friedland, Leonid Gurvits

SIAM J. Matrix Anal. Appl., July, 1994

Near-optimal nonholonomic motion planning for a system of coupled rigid bodies.

Chris Fernandes, Leonid Gurvits, Zexiang Li

IEEE Trans. Autom. Control., 1994

Max-Min Properties of Matrix Factor Norms.

Anne Greenbaum, Leonid Gurvits

SIAM J. Sci. Comput., 1994

Attitude Control of a Space Platform/Manipulator System Using Internal Motion.

Chris Fernandes, Leonid Gurvits, Zexiang Li

Int. J. Robotics Res., 1994

1993

Controlability by completions of partial upper triangular matrices.

Leonid Gurvits, Leiba Rodman, Tamir Shalom

Math. Control. Signals Syst., 1993

Rate of Approximation Results Motivated by Robust Neural Network Learning.

Christian Darken, Michael Donahue, Leonid Gurvits, Eduardo D. Sontag

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

Averaging approach to nonholonomic motion planning.

Leonid Gurvits

Proceedings of the 1992 IEEE International Conference on Robotics and Automation, 1992

1991

A variational approach to optimal nonholonomic motion planning.

Chris Fernandes, Leonid Gurvits, Zexiang Li

Proceedings of the 1991 IEEE International Conference on Robotics and Automation, 1991