Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Combinatorics hidden in hyperbolic polynomials and related topics

The famous Rado theorem on the rank of intersection of two matroids , where the first is matroid of transversals and the second is a geometric matroid, can be equivalently formulated in terms of determinantal polynomials Det(A_i x_i +...+A_n x_n), where A_i are PSD hermitian matrices. The main topic of this talk is a "hyperbolic" generalization of the Rado theorem . The main tool is a recent proof of the Lax conjecture. I will present various computer science applications of this result, mainly that similarly to the intersection of two matroids situation, the "hyperbolic" Rado conditions can be checked in deterministic oracle polynomial time. The main message of this talk is that hyperbolicity is hidden in many combinatorial and complexity-theoretic results . Time permit, I will pose a few open problems.

Type of Seminar:
Public Seminar
Dr. Leonid Gurvits
Los Alamos National Laboratory, USA
Jul 23, 2004   14:00

ETH-Zentrum, ETL K25, Physikstrasse 3, Zürich
Contact Person:

Prof. P.Parrilo
No downloadable files available.
Biographical Sketch:
- -