Upper Bounds on Matching Families in <formula formulatype="inline"> <tex Notation="TeX">$\BBZ_{pq}^{n}$</tex></formula>

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

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 Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , where Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> is the ring of integers modulo m, is an interesting problem. In this paper, we show an upper bound of O ((pq) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0.625n+0.125</sup> ) for the size of any matching family in Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">pq</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , 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 and coworkers.
BibTeX
@article{chee2013upper,
  author = {Yeow Meng Chee and San Ling and Huaxiong Wang and Liang Feng Zhang},
  title = {{Upper Bounds on Matching Families in \&lt;formula formulatype="inline"\&gt; \&lt;tex Notation="TeX"\&gt;$\textbackslash\{\}BBZ\_\{pq\}^\{n\}$\&lt;/tex\&gt;\&lt;/formula\&gt;}},
  journal = {IEEE Transactions on Information Theory},
  year = {2013},
  doi = {10.1109/tit.2013.2257918},
}

Loading related content...

Figure