## Combinatorics hidden in hyperbolic polynomials and related topics |
Back |

Abstract: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 |

Speaker:Dr. Leonid Gurvits Los Alamos National Laboratory, USA | |

Date/Time:Jul 23, 2004 14:00 | |

Location:ETH-Zentrum, ETL K25, Physikstrasse 3, Zürich | |

Contact Person:Prof. P.Parrilo | |

No downloadable files available. | |

Biographical Sketch:- - |