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.

See ECCC TR12-034

Back to list of Oded's choices.