2021/07/21 by Lin Zhu, Zhu, Lin, Wen Ming Li +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #11T71 #Coding theory and cryptography #Cooperative Communication and Network Coding #Cryptography and Security (cs.CR) #DNA and Biological Computing #E.4 #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2107.09830
openalex publication_date 2021/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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=p1α1p2α2⋯ prαr may result in an MVC with k≤ 2r 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<2r. 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=p1p2. In this paper, we study good numbers of the form m=p1α1p2α2. We show that if m=p1α1p2α2 is good, then any multiple of m of the form p1β1p2β2 must be good as well. Given a good number m=p1α1p2α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.