期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 68, 期 7, 页码 4378-4391出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2022.3158762
关键词
Codes; Reed-Muller codes; Linear codes; Protocols; Upper bound; Generators; Hamming weight; Reed-Muller codes; generalized covering radius; covering algorithm
资金
- Israel Science Foundation (ISF) [1052/18]
- German Israeli Project Cooperation (DIP) [PE2398/1-1]
This study focuses on the generalized covering radii of linear codes and their application in data-query protocols. It proves lower and upper bounds on the generalized covering radii of Reed-Muller codes, and also constructs a covering algorithm which can find corresponding codewords efficiently.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据