1301.0980

Total: 1

#1 Upper Bounds on Matching Families in $\mathbb{Z}_{pq}^n$ [PDF] [Copy] [Kimi] [REL]

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

\textit{Matching families} are one of the major ingredients in the construction of {\em 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 $\mathbb{Z}_m^n$, where $\mathbb{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 $\mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is valid when $n$ is a constant, $p\rightarrow \infty$ and $p/q\rightarrow 1$. Our result improves an upper bound of Dvir {\it et al.}

Subject: Information Theory

Publish: 2013-01-06 06:54:44 UTC