Information Theory Seminar

TITLE: Investigating the Fundamental Communication Burden of Cooperation

SPEAKER: Paul Cuff (Stanford University)

DATE: 11:30 AM - 12:30 PM, Friday, May 1, 2009

LOCATION: Sigma, 1L

ABSTRACT:
Communication is required to establish cooperative behavior in a network of nodes when relevant information is known to only some nodes in the network. Finding the minimum communication requirements can be posed as a network source coding problem, but rather than focus on sending data from one point to another with a fidelity constraint, we consider the communication needed to establish coordination that is summarized by a joint distribution of behavior among all nodes in the network. In addition to stating general results, we focus on the example of assigning tasks for distributed computation to computers in a network, in adversarial and non-adversarial settings.

Technology continues to move in the direction of parallel computation, whether it be in a computer or across the internet. Second order effects such as the communication needed to carry out a distributed algorithm have become a concern. In this light, we ask what the fundamental communication requirements are for distributing tasks. The model is simple: tasks are numbered; some nodes in the network are assigned tasks; others have to choose from the remaining unassigned tasks. However, finding the fundamental communication requirements, even in simple networks, proves to be challenging.

In the same vein as distributed algorithms, we look at the communication and secrecy needed to carry out cooperative behavior in a game theoretic setting. Claude Shannon identified the secret key requirements for secret communication without assuming any complexity restrictions. With game theory in mind, we find new objectives, other than sending secret information. These modified objectives can relax the secret key requirement without compromising perfect secrecy.

BIOGRAPHY:
Paul Cuff is a Ph.D candidate in Electrical Engineering at Stanford University, researching information theory with Prof. Tom Cover. He received a Bachelor's degree from Brigham Young University in 2004 and a Master's degree from Stanford University in 2006, both in Electrical Engineering. Mr. Cuff was awarded the ISIT 2008 Student Paper Award for his work titled "Communication Requirements for Generating Correlated Random Variables." He is a recipient of the National Defense Science and Engineering Graduate Fellowship and the Numerical Technologies Fellowship.