[Colloq] REMINDER: TODAY - 12noon - 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

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq