Combinatorial lower bounds for 3-query LDCs

Abstract

A code is called a $q$-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index $i$ and a received word $w$ close to an encoding of a message $x$, outputs $x_i$ by querying only at most $q$ coordinates of $w$. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for $3$-query binary LDCs of dimension $k$ and length $n$, the best known bounds are: $2^{k^{o(1)}}\ge n\ge \tilde{\Omega }(k^2)$. In this work, we take a second look at binary $3$-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of $\tilde{\Omega }(k^2)$ for the length of strong $3$-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to $2$-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.

10 pages