Skip to main content

New bounds for matching vector families

Author(s): Bhowmick, A; Dvir, Zeev; Lovett, S

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〉 = 0, and for any i ≠ j, 〈ui, vj〉 ≠ 0. An MV family is called q-restricted if inner products 〈ui, vj〉 take at most q different values. Our interest in MV families stems from their recent application in the construction of subexponential 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 behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154-1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1-16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71-86] 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 superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman.Ruzsa conjecture over ℤm.
Publication Date: 25-Sep-2014
Electronic Publication Date: 25-Sep-2014
Citation: Bhowmick, A, Dvir, Z, Lovett, S. (2014). New bounds for matching vector families. SIAM Journal on Computing, 43 (1654 - 1683. doi:10.1137/130932296
DOI: doi:10.1137/130932296
Pages: 1654 - 1683
Type of Material: Journal Article
Journal/Proceeding Title: SIAM Journal on Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.