Speaker: Jaikumar Radhakrishnan Tata Institute of Fundamental Research, India
Time: 2008-04-23 15:30-2008-04-23 16:30
Venue: FIT Building 4-603, Tsinghua University

Abstract:

 Let A and B be finite non-empty sets and (X,Y) a pair of random variables taking values in A times B. We consider communication protocols between two parties, Alice and Bob, for generating X and Y. Alice is provided an x in A generated according to the distribution of X, and is required to send a message to Bob in order to enable him to generate y in B, whose distribution is the same as that of Y|_{X=x}. Both parties have access to a shared random string generated in advance. Let T(X:Y) be the minimum (over all protocols) of the expected number of bits Alice needs to transmit to achieve this. We show that I[X:Y] <= T[X:Y] <= I[X:Y] + 2log_2 (I[X:Y]+1) + O(1). We also consider the worst-case communication required for this problem, where we seek to minimize the average number of bits Alice must transmit for the worst-case x in A. We show that the communication required in this case is related to the capacity C(E) of the channel E, derived from (X,Y), that maps x in X to the distributi on of Y|_{X=x}. We show that the required communication T(E) satisfies C(E) <= T(E) <= C(E) + 2log_2 (C(E)+1) + O(1). Using the first result, we derive a direct sum theorem in communication complexity that substantially improves the previous such result. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other. (This is joint work with Prahladh Harsha, Rahul Jain and David McAllester.)

Short Bio:
Jaikumar Radhakrishnan is a Professor in the School of Technology and Computer Science of the Tata Institute of Fundamental Research, Mumbai. 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 at CMC, 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 joined the Tata Institute of Fundamental Research in September 1991. He spent a year at the Japan Advanced Institute of Science and Technology (1992-93), a year at the Hebrew University (1996-97) and two years at the Toyota Technological Institute at Chicago (1994-96).
        Education: B.Tech. (IIT Kharagpur, 1985) Ph.D. (Rutgers University, 1991)
       Research Interests: Algorithms, Computational Complexity, Information Theory, Randomness and Computing, Quantum Computing Current affiliation: School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai.