Upper bounds on matching families in Znpq

Yeow Meng Chee, San Ling, Huaxiong Wang, Liang Feng Zhang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number6512552
Pages (from-to)5131-5139
Number of pages9
JournalIEEE Transactions on Information Theory
Issue number8
Publication statusPublished - 2013


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


Dive into the research topics of 'Upper bounds on matching families in Znpq'. Together they form a unique fingerprint.

Cite this