Upper bounds on matching families in Znpq

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

Research output: Contribution to journalArticle

Abstract

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
Volume59
Issue number8
DOIs
Publication statusPublished - 2013

Keywords

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

Fingerprint Dive into the research topics of 'Upper bounds on matching families in Z<sub>n</sub><sup>pq</sup>'. Together they form a unique fingerprint.

Cite this