Coding Theory: Combinatorial Batch Codes: Bounds and Constructions

Srimanta Bhattacharya (Indian Statistical Institute, Kolkata, India)

Sunday, 20.11.2016, 14:30

Taub 601

An (n, N, k, m, t)-batch code abstracts the following distributed database problem: n items are to be distributed among m servers in such a way that any (multi)set of k items can be retrieved by reading at most t items from each server with the condition that the total storage over m servers be bounded by N. Combinatorial batch codes (CBCs) are replication based variants, i.e., for these codes each of the N stored items is a copy of one of the n input data items. An (n, N, k, m)-CBC is called c-uniform if each of the n input data items is stored in exactly c servers.

Two optimization problems have been discussed in the context of CBCs. 1. Given n, m, k, we denote by N(n, k, m) minimum value of N such that there is an (n, N, k, m, t = 1)-CBC. 2. Given m, c, k, we denote by n(m, c, k) maximum value of n such that there is a c-uniform (n, cn, k, m, t = 1)- CBC. The problems of finding N(n, k, m) and n(m, c, k) seems to be difficult in general. In my talk, I will discuss some bounds and constructions related to these two problems.

Two optimization problems have been discussed in the context of CBCs. 1. Given n, m, k, we denote by N(n, k, m) minimum value of N such that there is an (n, N, k, m, t = 1)-CBC. 2. Given m, c, k, we denote by n(m, c, k) maximum value of n such that there is a c-uniform (n, cn, k, m, t = 1)- CBC. The problems of finding N(n, k, m) and n(m, c, k) seems to be difficult in general. In my talk, I will discuss some bounds and constructions related to these two problems.