Search

Baranyai’s theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all \(u\) -subsets of an \(n\) -element set into \({n-1\choose u-1}\) subfamilies such that each subfamily forms a partition of the \(n\) -element set, where \(n\) is divisible by \(u\) . In this paper, we present a coding-theoretic application of Baranyai’s theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh–Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh–Hadamard code. [ABSTRACT FROM PUBLISHER]

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 \BBZm^{n}, where \BBZm 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 \BBZpq^{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 and coworkers. [ABSTRACT FROM AUTHOR]