Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-012 | 2nd June 2010 02:28

Matching Vector Codes

RSS-Feed




Revision #1
Authors: Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin
Accepted on: 2nd June 2010 02:28
Downloads: 2925
Keywords: 


Abstract:

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to $\delta N$ locations. Recently a new class of locally decodable codes, based on families of vectors with restricted dot products has been discovered. We refer to those codes as Matching Vector (MV) codes. Several families of $(r,\delta,\Theta(r\delta))$-locally decodable MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suffered from having large values of $\epsilon=\Omega(r\delta).$ Codes with constant query complexity could only tolerate tiny amounts of error, and no MV codes of super-constant number of queries capable of tolerating a constant fraction of errors were known to exist. In this paper we develop a new view of matching vector codes and uncover certain similarities between MV codes and classical Reed Muller codes. Our view allows us to obtain a deeper insight into power and limitations of MV codes.
Specifically, we show that existing families of MV codes can be enhanced to
tolerate a nearly $1/8$ fraction of errors, independent of the value
of $r.$ Such enhancement comes at a price of a moderate increase in
the number of queries.
Our construction yields the first families of matching vector
codes of super-constant query complexity that can tolerate a
constant fraction of errors. Our codes are shorter than Reed Muller
LDCs for all values of $r\leq \log k / (\log \log k)^c,$ for some
constant $c.$
On the lower bound side we show that any MV code encodes messages of length $k$ to codewords of length at least $k2^{\Omega(\sqrt{\log k})}.$ Therefore MV codes do not improve upon Reed Muller locally decodable codes for $r\geq (\log k)^{\Omega(\sqrt{\log k})}.$


Paper:

TR10-012 | 27th January 2010 12:47

Matching Vector Codes





TR10-012
Authors: Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin
Publication: 27th January 2010 23:26
Downloads: 3463
Keywords: 


Abstract:

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to $\delta N$ locations. Recently a new class of locally decodable codes, based on families of vectors with restricted dot products has been discovered. We refer to those codes as Matching Vector (MV) codes. Several families of $(r,\delta,\Theta(r\delta))$-locally decodable MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suffered from having large values of $\epsilon=\Omega(r\delta).$ Codes with constant query complexity could only tolerate tiny amounts of error, and no MV codes of super-constant number of queries capable of tolerating a constant fraction of errors were known to exist. In this paper we develop a new view of matching vector codes and uncover certain similarities between MV codes and classical Reed Muller codes. Our view allows us to obtain a deeper insight into power and limitations of MV codes.
Specifically, we show that existing families of MV codes can be enhanced to
tolerate a nearly $1/8$ fraction of errors, independent of the value
of $r.$ Such enhancement comes at a price of a moderate increase in
the number of queries.
Our construction yields the first families of matching vector
codes of super-constant query complexity that can tolerate a
constant fraction of errors. Our codes are shorter than Reed Muller
LDCs for all values of $r\leq \log k / (\log \log k)^c,$ for some
constant $c.$
On the lower bound side we show that any MV code encodes messages of length $k$ to codewords of length at least $k2^{\Omega(\sqrt{\log k})}.$ Therefore MV codes do not improve upon Reed Muller locally decodable codes for $r\geq (\log k)^{\Omega(\sqrt{\log k})}.$



ISSN 1433-8092 | Imprint