[Colloq] Talk title: Computability of Maximum Entropy Distributions and its Applications in Approximation Algorithms | Mohit Singh, Microsoft Research, Redmond | 3/16/16 10:30-11:30am 366WVH

[Walker, Lashauna]

Talk title: Computability of Maximum Entropy Distributions and its Applications in  Approximation Algorithms
Speaker: Mohit Singh, Microsoft Research, Redmond
Date: 3/16/16  Time: 10:30-11:30am  Location: 366 WVH


Talk title: Computability of Maximum Entropy Distributions and its Applications in  Approximation Algorithms



Abstract:

In this talk I will discuss the problem of computing maximum entropy distributions over a discrete set of objects subject to observed marginals. While there has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, information theory, machine learning, combinatorics and algorithms, a rigorous and systematic study of how to compute such distributions had been lacking. In this talk, I will show that the problem of computing maximum entropy distributions, in a fairly general setting, is equivalent to a counting problem on the underlying set. One of the consequences of this equivalence is that, for several combinatorial settings, there is an efficient algorithm to compute max-entropy distributions.

I will also talk about applications of maximum entropy distributions to design approximation algorithms for discrete optimization problems including the Traveling Salesman Problem (TSP). These results include the first improvements over the classical Christofides' algorithm from 1970's for TSP on graph metrics.



Bio:

Mohit Singh is a researcher in the theory group at Microsoft Research, Redmond. His research interests include discrete optimization, approximation algorithms and convex optimization.  Previously, he was an Assistant Professor at School of Computer Science, McGill University from 2010-2011 and a post-doctoral researcher at Microsoft Research, New England from 2008-2009. He obtained his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University and his doctoral thesis received the Tucker prize in 2009 given by Mathematical Optimization Society. He has also received the best paper award for his work on the traveling salesman problem at Annual Symposium on Foundations of Computer Science (FOCS) 2011.


Thank You.

LaShauna Walker
Events and Administrative Specialist
College of Computer and Information Science
Northeastern University
617-373-2763
Facebook<https://www.facebook.com/ccisatnu?ref=hl> | Instagram<https://instagram.com/ccisatnu/> | LinkedIn<https://www.linkedin.com/groups/Northeastern-University-College-Computer-Information-1943637?gid=1943637&mostPopular=&trk=tyah&trkInfo=idx%3A1-1-1%2CtarId%3A1426606862845%2Ctas%3ANortheastern+University+College+of+Com> | Twitter<https://twitter.com/CCISatNU>