Blending EE with CS: an Interview with Devavrat Shah

Devavrat Shah

Jamieson Career Development Associate Professor, Laboratory for Information and Decision Systems

Devavrat Shah, third from right, meets informally with his group including (from left) Yuan Zhong, in Operations Research, Srikanth Jagabathula, graduate student in Electrical Engineering, Jonathan Perry, Computer Science graduate student, Vijay Subramanian, visiting research from the Hamilton Institute, Ireland, and Ammar Ammar, EECS graduate student.

Devavrat Shah, third from right, meets informally with his group including (from left) Yuan Zhong, in Operations Research at MIT, Srikanth Jagabathula, graduate student in electrical engineering, Jonathan Perry, computer science graduate student, Vijay Subramanian, visiting research scientist from the Hamilton Institute, Ireland, and Ammar Ammar, EECS graduate student.

Q. How would you describe yourself in terms of EE and CS and how do you find the blend lends itself to enhancing your research?

Devavrat Shah: As we know, interactions across EE, CS, Mathematics and Physics have resulted in explosive growth over the last century. A canonical example of a successful outcome of such multi-disciplinary interaction is the “Fast Fourier Transformation” — one of the top ten algorithms, the backbone of any signal processing device where signals are modeled as electromagnetic waves and its computational efficiency is based on insights from harmonic analysis. Roughly speaking, Physics and continuous Math, have formed the core of EE which primarily deals with “physical” system interfaces; while the primary system interface in CS has been “computational” with discrete Math at its foundation. Moreover, in the past few decades, the advent of large, inter-connected complex systems—such as the Internet and more recently data-centers, computation clouds—has resulted in an unusual level of interactions between EE and CS.

My primary research area, Network Algorithms, is central to this interaction: it is about designing simple-to-implement and efficient algorithms for large communication networks. This requires understanding the characteristics of the “physical” communication interface, inventing new algorithms and developing performance analytic methods using both discrete and continuous Math. My research has benefited immensely by embracing these diverse CS/EE interactions.

An excellent example of this fruitful interaction is embodied in our recently developed medium access algorithm that overcomes the major hurdle faced by an architect of high-bandwidth wireless access networks that will soon be the backbone of essentially any communications network. In doing so, we resolve a problem in distributed computation that has persisted over the past four decades. This is an example of a classical CS problem benefiting from an EE perspective.

On the other hand, a year back, we developed a reasonably accurate characterization of the limitation (information theoretic capacity region) of a large wireless network. Exact characterization of this limitation has been a notoriously difficult problem in network information theory—eluding reasonable progress since the seminal work of Claude Shannon in 1948. Philosophically, we were inspired by the basic premise of approximation in algorithmic theory and, in my opinion, our work has seeded this significant advance. By introducing the computational view in the context of constrained queuing networks, important insights have been developed in asymptotic queuing theory. These are examples of problems where EE and applied probability have benefited from a CS perspective. This experience with EE and CS interaction has convinced me that both have a lot to gain from each other.

In addition to EE and CS, Physics and Mathematics have played a major role in my research. For example, my involvement in developing theoretical foundations of message-passing algorithms, which provide a highly parallel computational interface and have been tremendously successful in communication and machine learning, was inspired by fantastic, bold conjectures from Statistical Physics. We have found spectral analysis on non-commutative groups providing important insights into inference of customer preferences (or ranking) from partial, information-limited data a problem found in Marketing, for example. Finally, simple insights from Large Deviations Theory have helped us design a CAD tool for circuits which has reduced simulation time from 40 days to 2 minutes!

Pages: 1 2

Leave a Reply

Replies which add to the content of this article in the EECS Newsletter are welcome. The Department reserves the right to moderate all comments. If you would like to provide any updated information please send an email to newsletter@eecs.mit.edu.