2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.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
