Upper Bounds on Matching Families in ${\mathbb{Z}}_{pq}^n$

Abstract

\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\to \infty$ and $p/q\to 1$. Our result improves an upper bound of Dvir {\it et al.}

10 pages