Events - Colloquia & Seminars

CCIS Colloquium Spring 2006

Generating correlated random variables with minimum transmission

Speaker: Jaikumar Radhakrishnan

Affiliation:
Toyota Technological Institute at Chicago and
Tata Institute of Fundamental Research, Mumbai

Date: Friday, March 31, 2006

Talk: 12:00 pm, 366 WVH

Abstract

Fix a pair (X,Y) of correlated random variables, each taking values in the set {0,1}^n. Let D be the marginal distribution of X, and D_x the conditional distribution of Y given X=x. We consider the following communication problem between two parties, Alice and Bob. Both parties know the distribution of (X,Y). Alice will be given a random input x distributed according to D. She needs to transmit a message to Bob so Bob can generate a value in {0,1}^n with distribution D_x. For example, Alice can send x across, and then Bob can pick a random value from the distribution D_x. This protocol, however, can be wasteful. For example, if X and Y are independent, Bob could have generated his value without any help from Alice. Let C be the minimum expected number of bits that Alice must transmit. We show that if Alice and Bob share a random string (independent of Alice's input), then

  I[X:Y] <= C <= I[X:Y] + O(log I[X:Y]),

where I[X:Y] = H[X] + H[Y] - H[XY] is the mutual information between the random variables X and Y. Before this work, an asymptotic version was shown by Bennett and Winter.

(If the shared random string is not available, then there are cases where Alice needs to send Omega(n) bits even though I[X:Y] = O(1).)

The main tool we use is a rejection sampling argument for generating one distribution from another. We will not assume any familiarity with information theory or communication complexity.

This is joint work with Prahladh Harsha, Rahul Jain and David McAllester.

Biography

Jaikumar Radhakrishnan is an Associate Professor at the School of Technology and Computer Science of the Tata Institute of Fundamental Research, Mumbai. He is currently a Visiting Professor at the Toyota Technological Institute at Chicago. He works in the area of Theoretical Computer Science, with emphasis on using combinatorial, probabilistic and information theoretic tools for showing lower bounds. He has contributed results in Approximation Algorithms, Circuit Complexity, Communication Complexity and Quantum Computing. He received his Bachelor's degree in Computer Science and Engineering from Indian Institute of Technology, Kharagpur, in 1985. After graduation, he worked in Calcutta for a year. He did his doctoral work at Rutgers University under the supervision of Endre Szemeredi and received his PhD in Computer Science in 1991. He spent a year at the Japan Advanced Institute of Science and Technology (1992-93) and a year at the Hebrew University (1996-97).