Complete Positivity in Information Theory (Yihan Zhang)

Abstract

Given a distribution P_{W_1, W_2, W_3}, when is it possible to construct an *arbitrarily long* sequence of random variables X_1, X_2, ..., X_M such that P_{X_i, X_j, X_k} = P_{W_1, W_2, W_3} for all 1 <= i < j < k <= M? We show that this is possible *if and only if* P_{W_1, W_2, W_3} is "completely positive", i.e., W_1, W_2, W_3 is a mixture of i.i.d. random variables. 

This theorem is surprisingly powerful and has found several applications in proving new coding theorems for *general* adversarial channels. If time permits, I will mention two examples: list decoding for oblivious adversarial channels and coding for general online adversarial channels. 

Based on joint work with Amitalok J. Budkuley (IIT Kharagpur) and Sidharth Jaggi (University of Bristol, CUHK).

Time

Speaker

Room