Constructions of Batch Codes via Finite Geometry
Dr. Nikita Polianskii
Skolkovo Institute of Science and Technology
Center for Computational and Data-Intensive Science and Engineering
A primitive k-batch code encodes a string x of length n into string y of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. The definition of such codes is motivated by applications to load balancing in distributed storage and private information retrieval. We develop new constructions of linear primitive batch codes based on finite geometries. In some parameter regimes, our codes have lower redundancy than previously known batch codes. Also, we prove new random coding bound on the redundancy of batch codes.
Nikita Polyanskii received his M.Sc. degree in Mathematics and his Ph.D. degree in Mathematics from the Lomonosov Moscow State University in 2013 and 2016, respectively. During 2015–2017, he was a researcher at the Institute for Information Transmission Problems and worked as a research engineer at Huawei R&D department in Moscow. Between 2017-2018, Nikita was a postdoctoral researcher at the Technion–Israel Institute of Technology. Since 2018 he has been a research scientist at the Skolkovo Institute of Science and Technology.