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

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.

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.

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.

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.

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.