ECE Colloquium - October 10

Dr. Changho Suh, Korea Advanced Institute of Science and Technology

Wednesday, October 10, 2012 - 10:00am - 12:00pm

CoRE Building Lecture Hall


The computation problem in networks represents a task-oriented communication setup where receivers wish to compute functions of multiple sources. While the problem has received considerable attention with applications in sensor networks and cloud computing scenarios, only the simplest setting has been well understood thus far which consists of a single receiver wanting a linear function of the sources: It is shown that the cut-set bound is tight in the single-receiver case. Beyond this case, we are still lacking in our understanding. Even for the next simplest setting which includes another receiver with the same demand, it is not known whether the cut-set bound is tight.

In this talk, I will present our recent progress on the problem of multicasting a linear function to multiple receivers. What we have shown is twofold. First we find that a function-matching network structure enables higher computation rates than the separation scheme can provide. Secondly we show that unlike the single-receiver case, the cut-set bound is not tight when multicasting a function. In the process of deriving this conclusion, we characterize the computing capacity of a two-transmitter two-receiver linear deterministic network where both receivers want to decode a mod-2 sum of two independent Bernoulli sources generated at the two transmitters.

Furthermore, we extend our results to a more general setting, thus characterizing the computing capacity of a class of L transmitter L receiver networks in the limit of L. We believe our achievability and converse theorem can be used as key tools to address general computation problems in networks.


Dr. Changho Suh is an Assistant Professor in the Department of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST) since 2012. He received the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in Electrical Engineering and Computer Sciences from UC-Berkeley in 2011, under the supervision of Prof. David Tse. From 2011 to 2012, he was a postdoctoral associate at the Research Laboratory of Electronics in MIT. From 2002 to 2006, he had been with the Telecommunication R&D Center, Samsung Electronics. Prof. Suh received the David J. Sakrison Memorial Prize for outstanding doctoral research from the UC-Berkeley EECS Department in 2011, the Best Student Paper Award of the IEEE International Symposium on Information Theory in 2009 and the Outstanding Graduate Student Instructor Award in 2010. He was awarded several fellowships, including the Vodafone U.S. Foundation Fellowship in 2006 and 2007; the Kwanjeong Educational Foundation Fellowship in 2009; and the Korea Government Fellowship from 1996 to 2002.