Revision #5 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Accepted on: 8th August 2013 00:41

Downloads: 963

Keywords:

A Matching Vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\ldots,u_t)$ and $V=(v_1,\ldots,v_t)$

where $u_i,v_j \in \mathbb Z_m^n$ with the following inner product pattern: for any $i$, $\langle u_i,v_i\rangle=0$, and

for any $i \neq j$, $\langle u_i,v_j\rangle \neq 0$. A MV family is called $q$-restricted if inner products $\langle u_i,v_j\rangle$ 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 first 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 $\mathbb Z_m$.

Theorem 1 now includes an improved bound for standard matching vector families in addition to restricted MV families

Revision #4 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Accepted on: 22nd March 2013 03:33

Downloads: 896

Keywords:

A Matching Vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\ldots,u_t)$ and $V=(v_1,\ldots,v_t)$

where $u_i,v_j \in \Z_m^n$ with the following inner product pattern: for any $i$, $\langle u_i,v_i\rangle=0$, and

for any $i \ne j$, $\langle u_i,v_j\rangle \ne 0$. A MV family is called $q$-restricted if inner products $\langle u_i,v_j\rangle$ 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 \cite{Efremenko} (based on an approach initiated by Yekhanin \cite{Y_nice}) gives the first sub-exponential

LDC with constant queries. It is based on a construction of a MV family of super-polynomial size by Grolmusz \cite{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 \cite{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 $\Z_m$.

At the heart of MV codes are families of vectors in $\mathbb Z_m^n$ with restricted inner products modulo $m$. More precisely, families $U = (u_1,\ldots,u_t)$, $V = (v_1,\ldots,v_t)$ with $u_i, v_j \in \mathbb Z_m^n$ such that $u_i \cdot v_i =0$ mod m for all $i \in [t]$ and $u_i \cdot v_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 $\mathbb Z_m$ that might be of independent interest.

Revision #3 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Accepted on: 6th November 2012 00:57

Downloads: 1768

Keywords:

A Matching Vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\ldots,u_t)$ and $V=(v_1,\ldots,v_t)$

where $u_i,v_j \in \Z_m^n$ with the following inner product pattern: for any $i$, $\langle u_i,v_i \rangle=0$, and

for any $i \ne j$, $\langle u_i,v_j\rangle \ne 0$. A MV family is called $q$-restricted if inner products $\langle u_i,v_j \rangle$ 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 first 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 $\Z_m$.

This version contains new upper bounds on MV families whose inner products lie in a small set.

Revision #2 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Accepted on: 20th April 2012 23:37

Downloads: 1152

Keywords:

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 $\mathbb Z_m^n$).

At the heart of MV codes are families of vectors in $\mathbb Z_m^n$ with restricted inner products modulo $m$. More precisely, families $U = (u_1,\ldots,u_t)$, $V = (v_1,\ldots,v_t)$ with $u_i, v_j \in \mathbb Z_m^n$ such that $u_i \cdot v_i =0$ mod m for all $i \in [t]$ and $u_i \cdot v_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 $\mathbb Z_m$ that might be of independent interest.

Intro now clarifies the different variants of MV codes and the scope of our lower bounds. Typos fixed.

Revision #1 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Accepted on: 5th April 2012 22:11

Downloads: 1235

Keywords:

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 $\mathbb Z_m^n$).

At the heart of MV codes are families of vectors in $\mathbb Z_m^n$ with restricted inner products modulo $m$. More precisely, families $U = (u_1,\ldots,u_t)$, $V = (v_1,\ldots,v_t)$ with $u_i, v_j \in \mathbb Z_m^n$ such that $u_i \cdot v_i =0$ mod m for all $i \in [t]$ and $u_i \cdot v_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 $\mathbb Z_m$ that might be of independent interest.

TR12-034 Authors: Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

Publication: 5th April 2012 20:10

Downloads: 1070

Keywords:

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 $\mathbb Z_m^n$).

At the heart of MV codes are families of vectors in $\mathbb Z_m^n$ with restricted inner products modulo $m$. More precisely, families $U = (u_1,\ldots,u_t)$, $V = (v_1,\ldots,v_t)$ with $u_i, v_j \in \mathbb Z_m^n$ such that $u_i \cdot v_i =0$ mod m for all $i \in [t]$ and $u_i \cdot v_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 $\mathbb Z_m$ that might be of independent interest.