Computer Science – Computational Complexity
Scientific paper
2012-04-05
Computer Science
Computational Complexity
Scientific paper
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 \in \Z_m^n$ such that $\ip{u_i}{v_i}=0 \mod m$ for all $i \in [t]$ and $\ip{u_i}{u_j} \neq 0 \mod m$ for $i \neq 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 $\Z_m^n$ that might be of independent interest.
Bhowmick Abhishek
Dvir Zeev
Lovett Shachar
No associations
LandOfFree
New Lower Bounds for Matching Vector Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Lower Bounds for Matching Vector Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Lower Bounds for Matching Vector Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-182914