Back to Faculty

Devavrat Shah

Associate Professor                 

Jamieson Career Development Professor, Electrical Engineering and Computer
IIT-Bombay, B. Tech, Computer Science and Engineering, 1999
Stanford, PhD, Computer Science, 2004


Biographical Overview

Devavrat Shah completed his PhD at Stanford University in October 2004. His thesis focused on the development of novel design and analytic methods for network algorithms.

Before coming to LIDS in the fall of 2005, he spent a year at the Mathematical Sciences Research Institute (MSRI) in Berkeley, California.  During this year of study, he was introduced to message-passing algorithms and graphical statistical inference. At LIDS, his research areas include statistical inference, network algorithms, and stochastics.


Research Areas

  • Network Algorithms
  • Stochastic Network Analysis
  • Gossip and Message-passing Algorithms
  • Graphical Models and Network Inference


Selected Publications

BOOK AND BOOK CHAPTERS
D. Shah, “Network scheduling and message-passing,” Performance Modeling and Engineering, Z. Liu and C. Xia, eds., a collection of tutorials from ACM Sigmetrics/Performance, 2008.

JOURNAL PAPERS
D. Shah and D. Wischik, “Heavy Traffic Analysis of Optimal Scheduling Algorithm for Switched Networks,” [undergoing revision].

D. Mosk Aoyama and D. Shah, “Fast Gossip Algorithms for Computing Separable Functions,” IEEE Transactions on Information Theory, 54(7), 2008.

M. Bayati, D. Shah, and M. Sharma, “Max-product for Maximum Weight Matching: Correctness, Convergence and LP Duality,” IEEE Transactions on Information Theory, 54(3), 2008.

S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Randomized Gossip Algorithms," IEEE Transactions on Information Theory, 52(6), 2006.

A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, “Optimal Throughput-Delay Tradeoff in Wireless Networks – Part I: The Fluid Model,” IEEE Transactions on Information Theory, 52(6), 2006.

CONFERENCE PAPERS
S. Rajagopalan, J. Shin, and D. Shah, “Network Adiabetic Theorem: An Efficient Randomized Protocol for Contention Resolution,” ACM Sigmetrics/Performance, 2009.

U. Niesen, P. Gupta, and D. Shah, “The Multicast Capacity Region of Large Wireless Networks,” IEEE Infocom, 2009.

J. Salez and D. Shah, “Belief Propagation: Optimal Algorithm For Random Assignment Problem,” SIAM SODA, 2009.

S. Jagabathula and D. Shah, “Inferring Popular Rankings Under Constrained Sensing,” Neural Information Processing Systems, 2008 (Best Student Paper Award).

K. Jung, Y. Lu, D. Shah, M. Sharma, and M. Squillante, “Revisiting Stochastic Loss Networks: Structures and Algorithms,” ACM Sigmetrics/Performance, 2008.

THESES
D. Shah, “Randomization and Heavy Traffic Theory: New Approaches for Design and Analysis of Switch Algorithms,” PhD Thesis, October 2004, Department of Computer Science, Stanford. Thesis Supervisor: Prof. Balaji Prabhakar.


Recent Educational Activities

COURSES
6.266: Network Algorithms
6.454: Graduate Seminar in Area I
6.975/15.070: Advanced Stochastic Processes
6.431: Probabilistic Systems Analysis and Applied Probability
6.454: Graduate Seminar in Area I
6.976: Network Algorithms
6.979/15.098: Special Seminar in Applied Probability and Stochastic Processes
6.431: Probabilistic Systems Analysis and Applied Probability
6.979/15.098: Special Seminar in Applied Probability and Stochastic Processes
6.976/ESD.937: Quantitative Foundations of Engineering Systems
6.431: Probabilistic Systems Analysis and Applied Probability

SEMINARS
LIDS Colloquium
Operations Research Center (ORC) Seminar
Theory of Computation (TOC) Colloquium
Stochastics and Applications Seminar


Awards and Grants

AWARDS, PRIZES, AND HONORS:
The President of India Gold Medal, IIT-Bombay 1999
IEEE Infocom Best Paper Award 2004
Informs George B. Dantzig Best Dissertation Award 2005
NSF CAREER Award 2006
ACM Sigmetrics/Performance Best Paper Award 2006
Jamieson Career Development Chair 2008
ACM Sigmetrics Rising Star Award 2008
Neural Information Processing Systems Best Student Paper Award 2008 (Supervised)

GRANTS
NSF Career Grant, “Implementable Network Algorithms via Randomization, Belief Propagation and Heavy Traffic Theory.”
NSF, “Future Optical Network Architectures,” joint with Vincent Chan and Asuman Ozdaglar (all at MIT).
NSF, “An Analytic Framework for Political and Social Change: Conflict, Beliefs, and Dynamics,” joint with Daron Acemoglu, Munther Dahleh, and Asuman Ozdaglar (all at MIT).
NSF, “Flow Level Models and the Design of Flow-aware Networks,” joint with Balaji Prabhakar (Stanford), John Tsitsiklis (MIT) and Maury Bramson (Univ. of Minnesota).
NSF, “Harnessing Statistical Physics for Computing and Communication,” joint with Michael Chertkov (Los Alamos National Lab) and Bart Selman (Cornell).
DARPA, “ITMANET, the FLOWs project,” joint with Andrea Goldsmith (Stanford) and Muriel Medard (MIT).
AFOSR, “Thermodynamics of Large Wireless Networks” joint with David Tse (UC Berkeley) and Piyush Gupta (Alcatel-Lucent Bell Labs).


Patents and Patent Applications Pending 

M. Medard, D. Shah, and J. Sunderarajan, “ARQ for Network Coding,” May 2008.
J. Barros, M. Medard, M. Mitzenmacher, D. Shah and J. Sunderarajan, “TCP Network Coding,” Oct. 2008.



Devavrat Shah

32-D670
77 Massachusetts Ave.,
Cambridge, MA 02139
617-324-0058 ph
617-253-3578 fax
devavrat@mit.edu

http://web.mit.edu/devavrat/www