On the Modulus in Matching Vector Codes
This work addresses the efficiency of locally decodable codes for error correction in coding theory, offering incremental theoretical progress by extending the known set of good moduli.
The paper tackles the problem of finding good moduli for matching vector codes (MVCs), which are the best known locally decodable codes, by showing that if a modulus of the form m=p1^α1 p2^α2 is good, then any multiple with the same prime divisors is also good, and provides an explicit method to generate infinitely many new good numbers, expanding from only finitely many previously known.
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)$ have been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{α_1}p_2^{α_2}\cdots p_r^{α_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 {\em good} if it is possible to have $k<2^r$. The good numbers yield more efficient MVCs. Prior to this work, there are only {\em 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^{α_1}p_2^{α_2}$. We show that if $m=p_1^{α_1}p_2^{α_2}$ is good, then any multiple of $m$ of the form $p_1^{β_1}p_2^{β_2}$ must be good as well. Given a good number $m=p_1^{α_1}p_2^{α_2}$, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields {\em infinitely many} new good numbers.