TY - GEN

T1 - New bounds for matching vector families

AU - Bhowmick, Abhishek

AU - Dvir, Zeev

AU - Lovett, Shachar

PY - 2013

Y1 - 2013

N2 - 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 [8] (based on an approach initiated by Yekhanin [24]) 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 [10] 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 [8]) 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.

AB - 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 [8] (based on an approach initiated by Yekhanin [24]) 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 [10] 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 [8]) 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.

KW - Locally decodable codes

KW - Matching vector families

KW - Restricted modular intersections

UR - http://www.scopus.com/inward/record.url?scp=84879801810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879801810&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488713

DO - 10.1145/2488608.2488713

M3 - Conference contribution

AN - SCOPUS:84879801810

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 823

EP - 832

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -