ECCC-Report TR12-034https://eccc.weizmann.ac.il/report/2012/034Comments and Revisions published for TR12-034en-usThu, 08 Aug 2013 00:41:32 +0300
Revision 5
| New Bounds for Matching Vector Families |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034#revision5A 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$.
Thu, 08 Aug 2013 00:41:32 +0300https://eccc.weizmann.ac.il/report/2012/034#revision5
Revision 4
| New Bounds for Matching Vector Families |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034#revision4A 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. Fri, 22 Mar 2013 03:33:42 +0200https://eccc.weizmann.ac.il/report/2012/034#revision4
Revision 3
| New Bounds for Matching Vector Families |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034#revision3A 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$.
Tue, 06 Nov 2012 00:57:18 +0200https://eccc.weizmann.ac.il/report/2012/034#revision3
Revision 2
| New Lower Bounds for Matching Vector Codes |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034#revision2We 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.
Fri, 20 Apr 2012 23:37:23 +0300https://eccc.weizmann.ac.il/report/2012/034#revision2
Revision 1
| New Lower Bounds for Matching Vector Codes |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034#revision1We 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.
Thu, 05 Apr 2012 22:11:22 +0300https://eccc.weizmann.ac.il/report/2012/034#revision1
Paper TR12-034
| New Lower Bounds for Matching Vector Codes |
Abhishek Bhowmick,
Zeev Dvir,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2012/034We 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.
Thu, 05 Apr 2012 20:10:27 +0300https://eccc.weizmann.ac.il/report/2012/034