On the Modulus in Matching Vector Codes. (22nd September 2021)

• Record Type: Journal Article
• Authors: Zhu, Lin; Li, Wen Ming; Zhang, Liang Feng
• Is Part Of: Computer journal. Volume 65:Number 12(2022)
• Page Start: 2991
• Page End: 2997
• Publication Date: 2021-09-22
• Subjects: matching vector codes -- locally decodable codes -- private information retrieval; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab121
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: A $k$ -query locally decodable code (LDC) $C$ allows one to encode any $n$ -symbol message $x$ as a codeword $C(x)$ of $N$ symbols such that each symbol of $x$ can be recovered by looking at $k$ symbols of $C(x)$, even if a constant fraction of $C(x)$ has been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_r^{\alpha _r}$ may result in an MVC with $k\leq 2^r$ and $N=\exp (\exp (O((\log n)^{1-1/r} (\log \log n)^{1/r})))$ . The $m$ is good if it is possible to have $k<2^r$ . The good numbers yield more efficient MVCs. Prior to this work, there are only finitely many good numbers. All of them were obtained via computer search and have the form $m=p_1p_2$ . In this paper, we study good numbers of the form $m=p_1^{\alpha _1}p_2^{\alpha _2}$ . We show that if $m=p_1^{\alpha _1}p_2^{\alpha _2}$ is good, then any multiple of $m$ of the form $p_1^{\beta _1}p_2^{\beta _2}$ must be good as well. Given a good number $m=p_1^{\alpha _1}p_2^{\alpha _2}$, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields infinitely many new good numbers.