A story of one convex relaxation, and of the related revelation
Speaker: Leonid Gurvits , Los Alamos National Laboratory
Date: February 11 2010
Time: 1:30PM to 2:30PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL: I will discuss remarkably short proofs of some inequalities for the
permanent of an n-by-n matrix including the celebrated permanental
Egorychev-Falikman and Schrijver Inequalities. Many of these
inequalities have applications to approximation algorithms for the
permanent. I'll also discuss some recent generalizations. Graduate
and undergraduate students are encouraged to attend: the stuff is
beautifully simple.
References:
M. Laurent and A. Schrijver, On Leonid Gurvits¢ proof for permanents,
2009, http://homepages.cwi.nl/ lex/files/perma5.pdf, to appear in
American Mathematical Monthly.
L. Gurvits, A polynomial-time algorithm to approximate the mixed
volume within a simply exponential factor. Discrete Comput. Geom. 41
(2009), no. 4, 533555.
L. Gurvits, On multivariate Newton-like inequalities,
http://arxiv.org/abs/0812.3687.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in February 2010
