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.
翻译：我们的研究广泛覆盖了射线代码的基本特性,即射线代码,这是储存、潜伏和存取等线性数据查询协议之间的取舍特征。我们证明,在Reed-Muller代码的广度覆盖射线代码上,以及在某些极端情况下发现其准确价值上下下限。在对线性数据查询协议的应用中,我们还构建了一种覆盖算法,作为空间中一组点的输入,并从Reed-Muller代码中找到一套相应的代码,这些代码与输入距离该代码广度覆盖半径的上界并不相距远。我们证明,算法在时间上是代码参数中的多元值。
相关内容
微信扫码咨询专知VIP会员