Combinatorics Seminar 2015

Speaker: Liang Feng Zhang (张良峰), ShanghaiTech University

Date: Wed, Oct 21, 2015

Time: 16:00 - 16:50

Venue: Middle Meeting Room

Title: Hypergraph-based locally decodable codes: A coding-theoretic application of Baranyai's theorem


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 talk, 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.

Slides: View slides