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 BBZmn, where BBZ m is the ring of integers modulo m, is an interesting problem. In this paper, we show an upper bound of O((pq0.625n+0.125) for the size of any matching family in BBZpqn, where p and q are two distinct primes. Our bound is valid when n is a constant, and 1. Our result improves an upper bound of Dvir and coworkers.
- Locally decodable codes (LDCs)
- matching families
- upper bound