Information Theory in the Crowd

Vinod Prabhakaran University of Illinois at Urbana-Champaign 123 Coordinated Science Laboratory Urbana, IL 61801
Tuesday, 20 Apr 2010 (all day)
A-212 (STCS Seminar Room)
In a short span in the 1940's Claude Shannon established the fields of information theory and modern cryptography which lie at the foundation of the digital era. While the founder's legacy continues to influence both fields, the central challenges facing them today are very different from the days of their origin. I will present recent work on both the fields.

The point-to-point communication problem Shannon introduced in his seminal paper founding the field of information theory is now thoroughly understood and it has had a tremendous impact on the design of communication systems. This has provided the theoretical underpinnings for the wireless communication revolution of the past two decades. What fundamentally limits the performance of all wireless communication networks today is interference -- a necessarily network phenomenon. I will discuss a modern view of interference: one which turns the root cause of interference, namely the broadcast nature of wireless transmissions, into an ally by exploiting the potential for cooperation between nodes. I will present information theoretically efficient communication schemes for canonical models of wireless networks that cover a range of issues in wireless networks.

In laying the foundations of modern cryptography, Shannon considered the problem of secure communication where two parties want to communicate while excluding a third-party eavesdropper. But more sophisticated problems in cryptography today involve protecting the privacy of collaborators from each other, rather than from an external eavesdropper, e.g., hospitals want to pool their patient databases and perform data-mining without breaching privacy laws which restrict them from sharing sensitive information. Secure multiparty computation is a theoretical framework for studying such problems. I will present the best available upperbound on the efficiency of an important class of problems called secure two-party sampling. The bound is based on a key tool we developed by generalizing the concept of common information in information theory.

Bio: Vinod Prabhakaran received his Ph.D. in December of 2007 from the EECS Department, University of California, Berkeley. Since then he has been a postdoctoral researcher at Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. His research interests are in information theory, wireless communication, cryptography,
distributed signal processing and communication. He has received a Commendation of the Senate of the Indian Institute of Science, Bangalore, the Tong Leong Lim Pre-Doctoral Prize and the Demetri Angelakos Memorial Achievement Award from the EECS Department, University of California, Berkeley.