Inferring Rankings under Constrained Sensing

June 15, 2009
Devavrat Shah | MIT

Motivated by applications like elections, network measurements, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings given constrained data. Specifically, we consider the problem of inferring a probability distribution over the space of permutations using its first order marginals. We characterize the precise conditions (in terms of the sparsity of the support of the
distribution) under which the distribution can be recovered. The question considered in this talk is thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing. Time permitting we shall discuss certain extensions in terms of robust formulation of the problem with a specific application as well as the tradeoff between partial information and recoverability.

Speaker Details

Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science at MIT. His research interests include statistical inference and network algorithms. He was co-awarded the IEEE INFOCOM best paper award in 2004 and ACM SIGMETRICS/Performance best paper award in 2006. He received 2005 George B. Dantzig best disseration award from the INFORMS. He is the recipient of the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms.