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 [Yek] and Efremenko [Efr] 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 in [DGY] where quasi-linear lower bounds were proved on their encoding length. Our work makes another step in this direction by proving two new lower bounds. The first is an unconditional quadratic lower bound, conjectured in [DGY], 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 {em conditional} super-polynomial lower bound for constant-query MV codes, assuming a well-known conjecture in additive combinatorics -- the Polynomial Freiman Rusza conjecture (over Znm). At the heart of MV codes are families of vectors in Znm with restricted inner products modulo m. More precisely, families U=(u1ut), V=(v1vt) with uivjZnm such that uivi=0 mod m for all i[t] and uivj=0 mod m for i=j . Our lower bounds for MV codes are obtained by improving the known {em 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 Zm that might be of independent interest.