[Colloq] Friday, March 31 - Jaikumar Radhakrishnan

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Jaikumar Radhakrishnan
Toyota Technological Institute at Chicago and
Tata Institute of Fundamental Research, Mumbai

Who will speak on:
Generating Correlated Random Variables with Minimum Transmission

Friday, March 31, 2006
12:00pm
366 West Village H
Northeastern University

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).

Host: Ravi Sundaram