New Lower Bounds for Matching Vector Codes
We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin (JACM 2008) and Efremenko (STOC 2009) and are the only known families of LDCs with a constant number of queries and sub-exponential encoding length. The systematic study of these codes, and their limitations, was initiated by Dvir et al (SIAM J. Comp. 2011) where quasi-linear lower bounds were proved on their encoding length. Our work makes another step in this direction by proving two new lower. The first is an unconditional quadratic lower bound, conjectured by Dvir et al, which is the first bound to exceed the known lower bounds for general constant-query LDCs (when the number of queries is greater than four). The second result is a conditional super-polynomial lower bound for constant-query MV codes, assuming a well-known conjecture in additive combinatorics -- the Polynomial Freimann Rusza conjecture (over $\Z_m^n$). At the heart of MV codes are families of vectors in $\Z_m^n$ with restricted inner products modulo $m$. More precisely, families $U = (u_1,...,u_t)$, $V = (v_1,...,v_t)$ with $u_i,v_j ∈ \Z_m^n$ such that $\ipu_iv_i=0 \mod m$ for all $i ∈ [t]$ and $\ipu_iu_j \neq 0 \mod m$ for $i \neq j$. Our lower bounds for MV codes are obtained by improving the known upper bounds on such families -- a question that arises independently in combinatorics in the context of set systems with restricted modular intersections. In the course of our proofs we develop certain tools for working with matrices over $\Z_m^n$ that might be of independent interest.