Index Codes from t-designs

Vortrag von Marco Calderini

Datum: 21.10.13  Zeit: 13.00 - 14.00  Raum:

Abstract: The index coding problem is described in the following scenario. There are m receivers, each with a request for a data packet from a set of n packets. A central server broadcasts data to the recipients, each of which is assumed to have some side-information. The goal of the sender is then to meet each request, minimizing the total number of transmissions, given knowledge of the each receiver’s side information. This number is typically lower if coding of data packets is performed by the sender.

Bar-Yossef et al. (2006) characterized the optimal transmission rate of scalar linear index codes for an ICSI instance by the so-called min-rank of the side-information hyper graph corresponding to that instance. It was shown by Peeters (1996) that computing the min-rank of a general graph is an NP-hard problem.

We will discuss how to use the t-designs to obtain an upper bound on the min-rank of the side-information hyper graph. Moreover we will see some security properties of an index code, in a scenario where an adversary is listening the transmission, focusing on the case when a projective plane of prime order is "contained" in the side-information.