New Lower Bounds for Matching Vector Codes

by Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett.

Oded's comments

I feel that the relation between upper bounds on Matching Vectors (MV) and lower bounds for Locally Decodable Codes (LDC) is not sufficiently clarified in the paper, and I wish to try to clarify it.

The foregoing relation refers to a specific method of constructing LDC (based on MV), which was used in all recent improvements regarding (constant-round) LDC (starting with Sergei Yekhanin's work). The general MV framework refers to a sequence of $K$ distinct $n$-ary vectors over $Z_m$ such that the inner product of two vectors equals zero if and only if these vectors are identical. Such a sequence yields an $m$-query LDC mapping $K$-bit strings to sequence of length $N=m^n$. Thus, upper bounds on $K$ as a function of $n$ (and $m$), yield lower bounds on $N$ in terms of $K$.

The MV framework has two instantiations. The generic one is just as described above. However, better LDC can be obtained by a more refined method that also refers to algebraic properies of the set $S$ that contains all values of inner products of different vectors; that is, one can always use $S=Z_m^*$, but better results are obtained when $S$ is smaller, and more so when it has a certain algebric structure. In these cases, the number of queries may be $|S|$ or even smaller.

The refined method is crucial for Sergei's work, since he used varying/growing values of $m$ (Mersenne-primes) but needs the number of queries to remain fixed (e.g., three). In contrast, Klim Efremenko fixes $m$ (e.g., $m=511$), and could have gotten a subexponentially long LDC also by the generic method, but such a LDC would have used 511 queries rather than three queries. (Actually, he could have had 15 queries with $m=15$.)

The current paper obtains lower bounds on constant-query LDCs that may be constructed by the generic MV method. Such a generic construction must have $m=O(1)$, which allows to treat $f(n)+c(m)$ as $f(n)$ and $c(m)f(n)$ as $O(f(n))$. Thus, $K < m^{(n/2)+O(log m)}$ yields $N > K^{2-o(1)}$, whereas $K < m^{c(m)(n/log n)}$ yields $N > K^{Omega(loglog K)}$. Indeed, the first example corresponds to an unconditional result that is presented in the paper, whereas the second example corresponds to a conditional result (i.e., a result that is based on a well-known conjecture in additive combinatorics).

Although the latter result is conditional and it refers to a specific way of constructing LDC, it does offer some evidence to the conjecture that LDC must have super-polynomial length.

The original abstract

See ECCC TR12-034

Back to list of Oded's choices.