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 gets as input a
set of points in space, and find a corresponding set of codewords from the
Reed-Muller code that are jointly not farther away from the input than the
upper bound on the generalized covering radius of the code. We prove that the
algorithm runs in time that is polynomial in the code parameters.