New Bounds for Matching Vector Families
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett · SIAM Journal on Computing · 2014
A matching vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\ldots,u_t)$ and $V=(v_1,\ldots,v_t)$ where $u_i$, $v_j \in \mathbb{Z}_m^n$ with the following inner product pattern: for any $i$, $\langle u_i,v_i\rangle=0$, and for any $i e j$, $\langle u_i,v_j\rangle e 0$. An MV family is called $q$-restricted if inner products $\langle u_i,v_j\rangle$ take at most $q$ different values. Our interest in MV families stems from their recent application in the construction of subexponential locally decodable codes (LDCs). There, $q$-restricted MV families are used to construct LDCs with $q$ queries, and there is special interest in the regime where $q$ is constant. When $m$ is a prime it is known that such constructions yield codes with exponential block length. However, for composite $m$ the behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154--1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1--16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71--86] modulo composite $m$. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When $q$ is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus $m$ is constant (as it is in the construction of Efremenko) we prove a superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman--Ruzsa conjecture over $\mathbb{Z}_m$.