Journal article
On the Generalized Covering Radii of Reed-Muller Codes
Abstract
We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that …
Authors
Elimelech D; Wei H; Schwartz M
Journal
IEEE Transactions on Information Theory, Vol. 68, No. 7, pp. 4378–4391
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Publication Date
July 1, 2022
DOI
10.1109/tit.2022.3158762
ISSN
0018-9448