Blind Index Coding

We introduce a problem formulation referred to as "blind index coding" (BIC). BIC generalizes the classic index coding formulation by modeling the message side-information provided to users as outputs of random channels whose statistics (but not realization) is known to the sender. This formulation is particularly applicable in distributed relay networks and caching networks where the side-information available to receivers cannot be precisely communicated all potential senders. 

For the BIC problem, we develop a new general outer bound by first proving it explicitly for the 3-user case, and then generalizing its construction to K users. We also propose a new approach to coding, which emphasizes the importance of XORing uncoded message bits in order to probabilistically align transmissions to available side-information.