pith. sign in

arxiv: 1301.0980 · v2 · pith:DPRMW6YLnew · submitted 2013-01-06 · 💻 cs.IT · math.IT

Upper Bounds on Matching Families in mathbb{Z}_(pq)^n

classification 💻 cs.IT math.IT
keywords matchingmathbbboundfamiliesupperconstantfamilyldcs
0
0 comments X
read the original 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\rightarrow \infty$ and $p/q\rightarrow 1$. Our result improves an upper bound of Dvir {\it et al.}

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.