Talk: Dr. Karan Khathuria (October 04, 2022 at 2:00 PM, Seminar room N2408)
On some batch code properties of the simplex code
Dr. Karan Khathuria
University of Tartu
A t-batch code is a method to store a data record in an encoded form on multiple servers in such a way that the bit-values in any batch of t positions from the record can be retrieved by decoding the bit-values in t disjoint groups of positions. More generally, a t-functional batch code can be used to retrieve any batch of t linear combinations of the stored bit-values. In 2017 by Wang et al., it was shown that the well-known binary simplex code of dimension k is a 2^(k-1)-batch code. The proof of that result is somewhat cumbersome, and the algorithm resulting from the proof requires to storing and using a database containing all the solutions for the cases where k <= 7. More recently, in 2020 Zhang et al., the authors conjecture that the k-dimensional simplex code is even a 2^(k-1)-functional batch code. In this talk, we give a simple, algorithmic proof of a result that falls halfway between the known result for the simplex code and the conjecture. Our approach is to relate the required properties of the simplex code to certain additive problems in finite abelian groups. In addition, we formulate a new conjecture for finite abelian groups that would imply the functional batch conjectures if true for groups of the form (Z_2)^k, and we prove that this new conjecture holds for the case of cyclic groups of prime order. This talk is based on a joint work with Henk D.L. Hollmann, Ago-Erik Riet and Vitaly Skachek.
Karan Khathuria received B.Sc. and M.Sc. degree in Mathematics from Centre for Excellence in Basic Sciences (Mumbai) in 2014 and 2016, respectively. He obtained his Ph.D. in Mathematics from the University of Zurich in 2020, under the supervision of Prof. Joachim Rosenthal. His research interests include Algebraic Cryptography, Coding Theory, Commutative Algebra, Computational Algebra and Algorithms.