Devavrat Shah
 |
Devavrat Shah |
Research Summary
My research is driven by a strong desire to better engineer socially integrated network where a typical user may connect through a smart-phone, socialize through Facebook, learn from Wikipedia and help bring socio-political change through Twitter. Such a “social network” is in dire need of better network infrastructure; a typical user is anxious for help to be able to cope with the information overload; and scalable computational systems are required to process large amounts of data. As a network theorist, my contributions towards addressing these challenges have been three fold: design better wireless access network, process social data and scalable algorithms that can operate in data center like facility.
First, we have developed medium access algorithm and network-wide co-operative coding architecture that provably provide optimal performance for wireless networks (see Medium Access and Scaling Laws).
Second, unlike human conversations, most interactions on “social networks” are recorded. This provides us with tremendous opportunity to learn about people and poses challenge of tackling information overload. We have developed methods and their practical realization to capture people’s choice from seemingly innocent data like transactions or clicking on one of many options (movies) on “display” (browsing a store). This can help better run businesses, provide recommendations and help make collaborative decisions (see People's Choice and Celect). To help cope with information overload, we have developed theory of searching information trail of people, e.g. Tweets on Twitter. Our search engine Trumor is a practical incarnation of our theory (see Searching The Source). (Want to learn more?)
Third, data centers and cloud facilities are emerging as canonical solution to store and process massive amounts of personal and social data. To operate such facilities while utilizing resources efficiently, we have developed theory of myopic resource scheduling algorithms to optimize non-myopic performance metric like system throughput or revenue (see Queue-based myopic policies). The algorithms for data processing operating in such facilities ought to be distributed and scalable. Belief propagation (BP) is one such algorithm which has been unexpectedly successful in practice. To explain the success and recognize limitations of BP, we have developed theoretical understanding of BP for inference/optimization by establishing connections to a class of linear programs (see Belief Propagation). We have also used insights from theory of probability to develop method for evaluating circuits that can be used in Computer Aided Design. This method speeds up the simulation necessary for circuit evaluation by 10000 times (e.g. simulation time goes from 2 months to 2 minutes (see Statistics for Circuits).
A salient feature of our work across this variety of networks is the use of distributed, iterative or the so-called message-passing procedures: as operational building blocks in communication networks (e.g. medium access), for efficient information processing in statistical networks (e.g. belief propagation) and as behavioral model in a social network (e.g. gossip algorithms).