Abstract:

 Suppose P, Q are probability distributions on the same sample space. Their relative entropy is defined as S(P||Q) = \sum_i P(i) \log (P(i) / Q(i)). The relative entropy is an important information theoretic quantity and is related to mutual information of two systems. The substate theorem states that if S(P||Q) < c, then there is a probability distribution P' close to P such that P'(i) / 2^{O(c)} < Q(i) for all i. A similar substate theorem holds for a pair of quantum states, under suitable definitions of the quantum information theoretic quantities.
        The substate theorem gives us a powerful tool for several questions in classical and quantum communcation and information. Very roughly, the power of the substate theorem comes from the fact that if the entropy of P relative to Q is at most c, then Q can be used as a substitute for P with a 2^{O(c)} loss in efficiency. Using the substate theorem, one can prove rounds versus privacy tradeoffs as well as rounds versus communication tradeoffs for several problems, as well as message compression and direct sum resuts in communication complexity, besides other information theoretic results.
        The talk will give an introduction to the classical and quantum statements of this theorem, together with an illustration of one of its applications. No prior knowledge of quantum information is required.

Short Bio:

Pranab Sen completed his PhD in Computer Science at the Tata Institute of Fundamental Research, Mumbai, India in 2001, under the supervision of Prof. Jaikumar Radhakrishnan. His thesis was on algebraic methods in computational complexity. The greater part of his thesis was on lower bounds on quantum computational complexity of data structure problems. After his PhD, he did postdoctoral research in quantum computation at Laboratoire de Recherche en Informatique, Universite de Paris-Sud, France in the group of Miklos Santha, and at the Institute of Quantum Computation, University of Waterloo, Canada. After that, he worked as a Research Staff Member in the Quantum Information Technology group at NEC Laboratories, Princeton, USA. He returned to India in August 2006 to join his alma mater, Tata Institute of Fundamental Research, he is a Reader in the School of Technology and Computer Science. His research interests lie in quantum computation and computational complexity.