Upper Bounds on Matching Families in Z(pq)(n)

作者：Chee Yeow Meng^*; Ling San; Wang Huaxiong; Zhang Liang Feng

来源：IEEE Transactions on Information Theory, 2013, 59(8): 5131-5139.

DOI：10.1109/TIT.2013.2257918

• Locally decodable codes (LDCs)
• matching families
• upper bound

Matching families are one of the major ingredients in the construction of 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 Z(m)(n), where Z(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 Z(pq)(n), where p and q a are two distinct primes. Our bound is valid when n is a constant, p -%26gt; infinity, and p/q -%26gt; 1. Our result improves an upper bound of Dvir and coworkers.

• 出版日期2013-8
• 单位南阳理工学院