## New Lower Bounds for Matching Vector Codes

by Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett.

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.