Technical Program

Paper Detail

Paper IDM.4.2
Paper Title Lifted Reed-Solomon Codes with Application to Batch Codes
Authors Lukas Holzbaur, Technical University of Munich, Germany; Rina Polyanskaya, Institute for Information Transmission Problems, Russia; Nikita Polyanskii, Technical University of Munich, Germany; Ilya Vorobyev, Skolkovo Institute of Science and Technology, Russia
Session M.4: Codes for Distributed Storage IV
Presentation Lecture
Track Coding for Storage and Memories
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to batch codes, a notion introduced in the context of private information retrieval and load-balancing in distributed storage systems. First, we improve the estimate of the code rate of lifted RS codes for lifting parameter $m\ge 3$ and large field size. Second, a new explicit construction of batch codes utilizing lifted RS codes is proposed. For some parameter regimes, our codes have a better trade-off between parameters than previously known batch codes.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!