Joint Colloquium Distinguished Lecture Series

What do Matroids have to do with Cell Phones?

Pablo Parrilo

Wednesday, April 14, 2010
306 Soda Hall (HP Auditorium)
4:00 - 5:00 pm

David Tse
Professor, EECS, UC Berkeley

Downloadable pdf


Cooperation between wireless devices is a powerful technique to improve the capacity of future systems. What is the maximum rate of information flow achievable by cooperation? In wired networks, this is answered by the max-flow min-cut theorem of Ford-Fulkerson in 1956. Due to the complex nature of signal interactions over the wireless meduim, generalizing this theorem to wireless networks has been a 30-year old open problem.  In this talk, we provide such a generalization. On the engineering side, our result provides architectural insights to the design of cooperation schemes. On the mathematical side, there is an interesting connection to matroid theory via the concept of linking systems introduced by Schrijver in the 70's.


He received the B.A.Sc. degree in systems design engineering from University of Waterloo, Canada in 1989, and the M.S. and Ph.D. degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1994 to 1995, he was a postdoctoral member of technical staff at A.T. & T. Bell Laboratories.

In 1995 he joined the faculty of the Department of Electrical Engineering and Computer Sciences, UC Berkeley. He received a 1967 NSERC 4-year graduate fellowship from the government of Canada in 1989, a NSF CAREER award in 1998, the Best Paper Awards at the Infocom 1998 and Infocom 2001 conferences, the Erlang Prize in 2000 from the INFORMS Applied Probability Society, the IEEE Communications and Information Theory Society Joint Paper Award in 2001, and the Information Theory Society Paper Award in 2003. He was the Technical Program co-chair of the International Symposium on Information Theory in 2004, and was an Associate Editor of the IEEE Transactions on Information Theory from 2001 to 2003. He is a coauthor, with Pramod Viswanath, of the text "Fundamentals of Wireless Communication". His research interests are in information theory, wireless communications and networking.

  Return to EECS Joint Colloquium