Campus Event Calendar
Event Entry
What and Who
Extended Formulations, Matrix Factorization and Communication Complexity - part II
Hans Raj Tiwary
Max-Planck-Institut für Informatik - D1
Lecture
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 1 June 2012
13:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
This will be the sequel to the talk given on 30th May (MPI 024, 16:15). The talk will be self contained and will not require attending the other talk.
In the other talk, (i.e. on 30th), I will prove a generalization of
Yannakakis' factorization theorem relating the complexity of any
Extended Formulation of a polytope P with the size of non-negative
factorization of the slack matrix of P.
In this talk I will provide some lower bounds on the size of
some polytopes like the perfect matching polytope and the TSP
polytope. The lower bounds for the latter answer a 20 year old open
question of Yannakakis
Contact
Saurabh Ray
--email hidden
passcode not visible
logged in users only
Saurabh Ray, 05/29/2012 13:54
Saurabh Ray, 05/29/2012 13:54 -- Created document.
Saurabh Ray, 05/29/2012 13:54 -- Created document.