|
Sujay Sanghavi
Postdoctoral Associate, MIT.
Member of the Stochastic Systems Group (SSG),
Laboratory for Information and Decision Systems (LIDS).
MIT, Room 32-D580
77 Mass. Ave
Cambridge, MA 02139
(617) 253-3816
|
Brief Biography
I completed my B. Tech in Electrical Engineering from IIT Bombay in 2000,
after which I joined the University of Illinois at Urbana-Champaign.
There I obtained my MS in Electrical Engineering in 2002, MS in Math
in 2005, and PhD in Electrical Engineering in 2006. My graduate
research focused on communication network algorithms, and my advisor
was Prof. Bruce Hajek. I was awarded the Perry Fellowship in 2002-3
and the Mavis Fellowship in 2004-5. Besides coursework and research, I
had the opportunity to intern in INRIA, Sophia-Antipolis and Microsoft
Research. I was the co-instructor of ECE 413, the senior-level
undergraduate course in Probability at UIUC, in Spring 2006. I also
organized the first CSL Student Conference in May 2006; this has now
become a regular feature at UIUC. After obtaining my PhD, I joined
Prof. Alan Willsky's Stochastic Systems Group at LIDS, MIT, as a
postdoc. I currently work on algorithms for large-scale inference and
learning. My primary research interests are in probability and
optimization, as applied to the design and analyis of distributed
algorithms in networks, communications and signal processing.
Selected Publications
My research has focused on the design and analysis of large-scale
distributed algorithms. The following is a selected list of papers,
with a short description for each. Some are the latest versions of journal
submissions.
NEW Tightness of LP via Max-product Belief
Propagation Sujay Sanghavi, Devavrat Shah
Submitted.
Shows that for certain random instances of the weighted independent set problem, the (simple,
edge-based) LP relaxation is tight with high probability. Uses belief propagation as a proof
technique.
Gossiping with Multiple Messages,
Sujay Sanghavi, Bruce Hajek, Laurent Massoulie
Accepted to
IEEE Transactions on Information Theory
Preliminary version:
INFOCOM 2007
An analytical model of peer-to-peer file sharing systems, quantifying
the speedup in dissemination obtained from splitting the file into
pieces. Models the spread of individual pieces, and quanitifies the
effect of local piece selection algorithms on global
performance.
Belief Propagation and LP
Relxation for Weighted Matching in General graphs Sujay Sanghavi,
Dmitry
Malioutov, Alan Willsky
Preliminary versions: NIPS 2007, ITW 2007
Analyzes the max-product version of loopy belief propgation (BP) for
arbitrary weighted matching problems on general graphs. Shows
that BP succeeds if and only if the LP relaxation of the
problem has no fractional optima.
Intermediate Performance of Rateless
Codes Sujay Sanghavi
Preliminary version: Information Theory Workshop ITW 2007, Tahoe
Investigates the extent to which partial recovery is possible
for fountain codes, in the case where the number of recived parities
is insufficient for full recovery. Focuses on the standard iterative
decoder.
Distributed Link Scheduling with
Constant Overhead Sujay Sanghavi, Loc Bui, R. Srikant
Preliminary version: SIGMETRICS 2007. Submitted journal version
Develops the first constant-overhead scheduling algorithms that can
capture any a-priori fixed fraction of the network capacity. Most
wireless scheduling protocols attempt to capture the entire capacity
region, and hence have overheads that scale with network size. Our
overheads scale with the fraction, but are independent of network
size. Journal version contains extensions to multi-hop traffic with
congestion control.
A New Mechanism for the Free-rider
Problem Sujay Sanghavi, Bruce Hajek
Accepted to IEEE
Transactions on Automatic Control
Preliminary version: P2PECON
2005
The correct level of a continuous-valued public good needs to be
produced at a certain cost, and will then be available to all
users. Users try to maximize their personal utility minus
contrinutions. We design a incentive/pricing mechanism that ensures
optimal provisioning at all Nash equilibria. Iterated best response
updates globally converge to some Nash equilibrium.