2013/01/06 by Yeow Meng Chee, Chee, Yeow Meng, San Ling +5
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Limits and Structures in Graph Theory #cs.IT #graph theory and CDMA systems #math.IT #msc:94B65
paper · pdf · doi:10.48550/arxiv.1301.0980
10 pages
arxiv created 2013/03/29 · arxiv updated 2013/04/01
Matching families are one of the major ingredients in the construction of \em locally decodable codes (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in ℤmn, where ℤm is the ring of integers modulo m, is an interesting problem. In this paper, we show an upper bound of O((pq)0.625n+0.125) for the size of any matching family in ℤpqn, where p and q are two distinct primes. Our bound is valid when n is a constant, p→ ∞ and p/q→ 1. Our result improves an upper bound of Dvir \it et al.