To refer to this page use:
|Abstract:||A Matching Vector (MV) family modulo m is a pair of ordered lists U = (u1,..., ut) and V = (v1,...,vt) where ui, vj ∈ ℤn m with the following inner product pattern: for any i, (ui, vi)i = 0, and for any i ≠ j, (ui, vi)≠ 0. A MV family is called q-restricted if inner products hui; vji take at most q different values. Our interest in MV families stems from their recent application in the construction of sub-exponential 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 behaviour is dramatically different. A recent work by Efremenko  (based on an approach initiated by Yekhanin ) gives the rst sub-exponential LDC with constant queries. It is based on a construction of a MV family of super-polynomial size by Grolmusz  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 super-polynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman-Ruzsa conjecture over ℤm.|
|Electronic Publication Date:||2013|
|Citation:||Bhowmick, A, Dvir, Z, Lovett, S. (2013). New bounds for matching vector families. 823 - 832. doi:10.1145/2488608.2488713|
|Pages:||823 - 832|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||45th Annual ACM Symposium on Theory of Computing, STOC 2013|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.