Devavrat Shah – All Publications

Book, Book chapter and Survey

D. Shah, Message-passing in stochastic processing networks, Surveys in Operations Research and Management Science, 2011.

D. Shah, Gossip Algorithms, Foundations and Trends in Networking, 2008. The monograph can be purchased here FnT.

D. Shah, Network scheduling and message-passing, Performance Modeling and Engineering, Editors Z. Liu and C. Xia, a collection of tutorials from ACM SIGMETRICS/Performance, 2008.

Pre-print/Submitted

V. Farias, S. Jagabathula and D. Shah, Sparse Choice Model, Preprint, Submitted September 2011.

D. Shah, J. N. Tsitsiklis and Y. Zhong, Qualitative properties of alpha-fair policies in bandwidth-sharing networks, Preprint, 2011.

V. Farias, S. Jagabathula and D. Shah, A Nonparametric Approach to Modeling Choice with Limited Data, Under review for Management Science, Submitted in October 2009, revised in October 2010 and June 2011.

2011

D. Karger, S. Oh and D. Shah, Iterative learning for reliable crowd-sourcing systems, accepted to appear in Proceedings of NIPS, 2011.

D. Gamarnik, D. Shah and Y. Wei, Belief propagation for network flow: convergence and correctness, accepted to appear in Operations Research, 2011.

D. Shah, J. Shin and P. Tetali, Medium access using queues, accepted to appear in Proceedings of IEEE FOCS, 2011.

D. Shah and D. Wischik, Fluid models of congestion collapse in overloaded switched networks, accepted to appear in Queueing Systems, 2011.

D. Shah and J. Shin, Randomized scheduling algorithm for queueing networks, accepted to appear in The Annals of Applied Probability, 2011.

S. Jagabathula and D. Shah, Inferring rankings using constrained sensing, accepted to appear in IEEE Transactions on Information Theory, 2011.

D. Shah, D. N. C. Tse and J. N. Tsitsiklis, Hardness of Low Delay Network Scheduling, accepted to appear in IEEE Transactions on Information Theory, 2011.

D. Shah and D. Wischik, Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse, accepted to appear in The Annals of Applied Probability, 2011.

D. Shah, J. N. Tsitsiklis and Y. Zhong, Optimal scaling of average queue sizes in an input-queued switch: an open problem, Queueing Systems, 2011.

D. Shah and T. Zaman, Rumors in a network: who's the culprit?, IEEE Transactions on Information Theory, 2011.

S. Jagabathula and D. Shah, Fair scheduling in networks through packet election, IEEE Transactions on Information Theory, 2011.

S. Rajagopalan and D. Shah, Distributed averaging in dynamic networks, IEEE Journal of Selected Topics in Signal Processing, 2011.

S. Bodas and D. Shah, Fast averaging, Proceedings of ISIT, 2011.

2010

L. Jiang, D. Shah, J. Shin and J. Walrand, Distributed Random Access Algorithm: Scheduling and Congestion Control, IEEE Transactions on Information Theory, 2010.

O. Ayaso, D. Shah and M. Dahleh, Information Theoretic Bounds for Distributed Computation over Networks of Point-to-Point Channels, IEEE Transactions on Information Theory, 2010.

D. Shah and T. Zaman, Detecting Sources of Viruses in Network: Theory and Application, Proceedings of ACM SIGMETRICS, 2010.

D. Shah and J. Shin, Dynamics in Congestion Games, Proceedings of ACM SIGMETRICS, 2010.

D. Shah, J. N. Tsitsiklis and Y. Zhong, Qualitative Properties of alpha weighted scheduling policies, Proceedings of ACM SIGMETRICS, 2010.

C. Moallemi and D. Shah, On the Flow level dynamics of packet-switched network, Proceedings of ACM SIGMETRICS, 2010.

V. Doshi, D. Shah, M. Medard and M. Effros, Functional Compression through Graph Coloring, IEEE Transactions on Information Theory, 2010.

D. Mosk-aoyama, T. Roughgarden and D. Shah, Fully Distributed Algorithms for Convex Optimization Problems, SIAM Journal on Optimization, 2010.

M. Tikekar, M. Qazi, L. Dolecek, D. Shah and A. Chandrakasen, Loop Flattening and Spherical Importance Sampling: A Highly Efficient Model Reduction Techniques For SRAM Yield Analysis, Proceedings of DATE, 2010.

D. Gamarnik, D. Shah and Y. Wei, Belief Propagation for Min-Cost Network Flow: Convergence & Correctness, Proceedings of SODA, 2010.

2009

K. Jung, D. Shah and J. Shin, Minimizing the rate of convergence for iterative algorithms, IEEE Transactions on Information Theory, 2009.

S. Sanghavi, D. Shah and A. Willsky, Message-passing for Max-weight independent set, IEEE Transactions on Information Theory, 2009.

U. Niesen, P. Gupta and D. Shah, Balanced Unicast and Multicast Capacity Regions of Large Wireless Networks, IEEE Transaction on Information Theory, 2009.

U. Niesen, P. Gupta and D. Shah, Capacity scaling for arbitrary wireless networks, IEEE Transaction on Information Theory, 2009.

K. Jung, P. Kohli, and D. Shah, Local Rules for Global MAP: When Do They Work, Proceedingsof NIPS, 2009.

V. Farias, S. Jagabathula and D. Shah, A Data Driven Approach to Modeling Choice, Proceedings of NIPS, 2009.

S. Jagabathula and D. Shah, Conditions for Recovery of Rankings from Partial Information, NIPS Workshop on Advances in Ranking, 2009.

D. Shah and T. Zaman, Rumor in a network: Who's the culprit?", Proceedings of NIPS Workshop on Analyzing Networks and Learning with Graphs, 2009.

S. Rajagopalan, D. Shah and J. Shin, Network adiabatic theorem: an efficient randomized protocol for contention resolution, Proceedings of ACM SIGMETRICS, 2009.

U. Niesen, D. Shah and G. Wornell, Adaptive alternating minimization algorithm, IEEE Transactions on Information Theory, 2009.

J. Sundararajan, D. Shah, M. Medard, M. Mitzenmacher and J. Barros, Network coding meets TCP, Proceedings of INFOCOM, 2009.

J. Salez and D. Shah, Belief propagation: optimal algorithm for random assignment problem, Mathematics of Operations Research, Vol. 32, No. 2, 2009.

S. Sanghavi and D. Shah, Tightness of LP via Max-product Belief Propagation, Accepted in AISTAT (absent from proceedings due to our inability to attend meeting), 2009.

R. Gummadi, K. Jung, D. Shah and R. Sreenivas, Computing the Capacity Region of a Wireless Network, Proceedings of INFOCOM, 2009.

2008

D. Shah and J. N. Tsitsiklis, Bin packing with queues, Journal of Applied Probability, 2008.

S. Jagabathula and D. Shah, Inferring popular rankings under constrained sensing, Proceedings of NIPS, 2008.

S. Sanghavi, D. Shah and A. Willsky, Message-passing for Max-weight independent set, Proceedings of NIPS, 2008.

R. Madan, D. Shah and O. Leveque, Product multi-commodity flow in wireless networks, IEEE Transactions on Information Theory, 2008.

L. Dolecek, M. Qazi, A. Chandrakasen and D. Shah, Breaking the Simulation Barrier: SRAM Evaluation Through Norm Minimization, Proceedings of ICCAD, 2008.

O. Ayaso, D. Shah and M. Dahleh, Counting Bits for Distributed Function Computation, Proceedings of ISIT, 2008.

J. Sundararajan, D. Shah and M. Medard, ARQ for Network Coding, Proceedings of ISIT, 2008.

A. Eryilmaz, A. Ozdaglar, D. Shah and E. Modiano, Cross-Layer Algorithms for the Optimal Control of Multi-hop Wireless Networks, IEEE/ACM Transactions on Networking, 2008.

K. Jung, Y. Lu, D. Shah, M. Sharma and M. Squillante, Revisiting stochastic loss networks: structures and algorithms, Proceedings of ACM SIGMETRICSPerformance/, 2008.

S. Jagabathula and D. Shah, Optimal delay scheduling in networks with arbitrary constraints, Proceedings of ACM SIGMETRICS, 2008.

D. Shah and D. Wischik, Lower bound and optimality in switched networks, Proceedings of Allerton Conference on Communication, Control and Computation, 2008.

M. Bayati, D. Shah and M. Sharma, Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality, IEEE Transactions on Information Theory, 2008.

D. Mosk-aoyama and D. Shah, Fast gossip algorithm for computing separable function, IEEE Transactions on Information Theory, 2008.

H. Waisanen, D. Shah and M. Dahleh, A Dynamic Pickup and Delivery Problem in Mobile Networks under Information Constraints, IEEE Transactions on Automatic Control, 2008.

S. Jagabathula, V. Doshi and D. Shah, Fair scheduling through packet election, Proceedings of INFOCOM, 2008.

J. Salez and D. Shah, Optimality of belief propagation for random assignment problem, Proceedings of SODA, 2008.

R. Gummadi, K. Jung, D. Shah and R. Sreenivas, Feasible rate allocation in wireless networks, Proceedings of INFOCOM, 2008.

2007

K. Jung and D. Shah, Local Approximate Inference Algorithms for Minor Excluded Graphs, Proceedings of NIPS, 2007.

M. Bayati, B. Prabhakar, D. Shah and M. Sharma, Iterative Scheduling Algorithms, Proceedings of INFOCOM, 2007.

D. Shah and S. Shakkottai, Oblivious Routing with Mobile Fusion Centers over a Sensor Network, Proceedings of INFOCOM, 2007.

J. Sunderarajan, M. Medard, M. Kim, A. Eryilmaz, D. Shah and R. Koetter, Network coding in a multi-cast switch, Proceedings of INFOCOM, 2007.

J. Mammen and D. Shah, Throughput and Delay in Random Wireless Networks with Restricted Mobility, IEEE Transactions on Information Theory, 2007.

D. Mosk-aoyama, T. Roughgarden and D. Shah, Fully Distributed Algorithms for Convex Optimization Problems, Proceedings of DISC, 2007.

V. Doshi, D. Shah and M. Medard, ource Coding with Distortion through Graph Coloring, Proceedings of ISIT, 2007.

P. Giaccone, E. Leonardi and D. Shah, Throughput Region in Finite-Buffered Networks, IEEE Transactions on Parallel and Distributed Systems, 2007.

A. Montanari and D. Shah, Counting Good Truth Assignment in Random k-SAT, Proceedings of SODA, 2007.

2006

S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, Randomized Gossip Algorithms, IEEE Transactions on Information Theory & IEEE/ACM Transactions on Networking, 2006.

A. El Gamal, J. Mammen, B. Prabhakar and D. Shah, Throughput and Delay in wireless networks – Part II: Constant-size packet, IEEE Transactions on Information Theory, 2006.

A. El Gamal, J. Mammen, B. Prabhakar and D. Shah, Throughput and Delay in wireless networks – Part I: Fluid case, IEEE Transactions on Information Theory & IEEE/ACM Transactions on Networking, 2006.

E. Modiano, D. Shah and G. Zussman, Maximizing throughput in wireless networks via Gossip, Proceedings of ACM SIGMETRICS/Performance,2006.

U. Niesen, U. Erez, D. Shah and G. Wornell, Rate-less Codes for Multi-Access Channels, Proceedings of Globecom, 2006.

D. Mosk-Aoyama and D. Shah, Information Dissemination via Network Coding, Proceedings of ISIT, 2006.

R. Madan, D. Shah and O. Leveque, Uniform Multi-commodity Flow in Wireless Networks with Gaussian Fading Channels, Proceedings of ISIT, 2006.

M. Bayati, D. Shah and M. Sharma, A simple max-product maximum weight matching algorithm and the auction algorithm, Proceedings of ISIT, 2006.

D. Mosk-aoyama and D. Shah, Computing separable function via Gossip, Proceedings of PODC, 2006.

D. Shah and D. Wischik, Optimal Scheduling Algorithms for Input-Queued Switches, Proceedings of INFOCOM, 2006.

2005

S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, Gossip algorithms: design, analysis and applications, Proceedings of INFOCOM, 2005.

Y. Ganjali, A. Keshavarzian and D. Shah, Cell switching versus packet switching in input queued switches, IEEE/ACM Transactions on Networking, 2005.

M. Bayati, D. Shah and M. Sharma, Maximum weight matching via max-product belief propagation, Proceedings of ISIT, 2005.

S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, Mixing Times for Random Walks on Geometric Random Graphs, Proceedings of ANALCO, 2005.

2004

J. Mammen and D. Shah, Throughput and delay in random wireless networks: 1-D mobility is just as good as 2-D, Proceedings of ISIT, 2004.

A. El Gamal, J. Mammen, B. Prabhakar and D. Shah, Throughput and delay tradeoff in wireless networks, Proceedings of INFOCOM, 2004.

P. Giaccone, E. Leonardi, B. Prabhakar and D. Shah, Delay bounds for combined input-output queued switches with low speedup, Performance Evaluation, 2004.

N. Kumar, R. Pan and D. Shah, Fair scheduling in input-queued switches under inadmissible traffic, Proceedings of Globecom, 2004.

2003

D. Shah, S. Iyer, B. Prabhakar and N. McKeown, Maintaining Statistics Counters in Router Line Cards, IEEE Micro, 2003.

G. Aggarwal, R. Motwani, D. Shah and A. Zhu, Switch scheduling via edge coloring, Proceedings of FOCS, 2003.

Y. Ganjali, A. Keshavarzian and D. Shah, Input queued switches: cell switching v/s packet switching, Proceedings of INFOCOM, 2003.

D. Shah, matching is good enough, Proceedings of Globecom, 2003.

P. Giaccone, B. Prabhakar and D. Shah, Randomized scheduling algorithms for high-aggregate bandwidth switches, IEEE JSAC, 2003.

2002

M. Mitzenmacher, B. Prabhakar and D. Shah, Balls and Bins with Memory, Proceedings of FOCS, 2002.

D. Shah and M. Kopikare, Delay bounds for approximate maximum weight matching algorithms for input-queued switches, Proceedings of INFOCOM, 2002.

P. Giaccone, B. Prabhakar and D. Shah, Towards Simple, High- Performance Schedulers for High-Aggregate Bandwidth Switches, Proceedings of INFOCOM, 2002.

1998-2001

D. Shah, Stable algorithms for input-queued switches, Proceedings of Allerton Conference, 2001.

D. Shah and P. Gupta, Fast Updating Algorithms for TCAMs, Proceedings of Hot Interconnects IX, 2000.

P. Shenoy, J. R. Haritsa, S. Sudarshan, G. Bhalotia, M. Bawa and D. Shah, Turbo-charging Vertical Mining of Large Databases, Proceedings of SIGMOD, 2000.

D. Shah, Laks V. S. Lakshmanan, K. Ramamritham and S. Sudarshan, [http:web.mit.edudevavratwwwdb1.ps Interestingness and Pruning of Mined Patterns, Proceedings SIGMOD workshop on research issues in Data Mining and Knowledge Discovery/, 1999.