July 28, 2021

Malware Protection

Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

On the Modulus in Matching Vector Codes. (arXiv:2107.09830v1 [cs.IT])

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^{alpha_1}p_2^{alpha_2}cdots p_r^{alpha_r}$ may result in an MVC with
$kleq 2^r$ and $N=exp(exp(O((log n)^{1-1/r} (loglog 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^{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
{em infinitely many} new good numbers.