Name
Abstract | ||
|---|---|---|
An (r;; )-locally decodable code encodes a k-bit message x to an N-bit codeword C(x); such that for every i2 (k); the i-th message bit can be recovered with probability 1 ; by a randomized decoding procedure that queries only r bits, even if the codeword C(x) is corrupted in up to 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;; ( r ))-locally decodable MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suered from having large values of = ( r ), which meant that r -query MV codes could only handle error-rates below 1 r . Thus larger query complexity gave shorter length codes but at the price of less error-tolerance. 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 present 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 deeper insights into the power and limitations of MV codes. Specically, 1. We show that existing families of MV codes can be enhanced to tolerate a large constant fraction of errors, independent of the number of queries. Such enhancement comes at a price of a moderate increase in the number of queries; 2. Our construction yields the rst 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 logk=(log logk) c ; for some constant c; 3. We show that any MV code encodes messages of length k to codewords of length at least k2 ( p log k) : Therefore MV codes do not improve upon Reed Muller LDCs forr (logk) ( p log k) : |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/FOCS.2010.73 | Foundations of Computer Science |
Keywords | Field | DocType |
matching vector,matching vector codes,decodable code,classical reed muller code,new class,certain similarity,codeword length,message bit,certain parameter setting,mv code,new view,decoding,vectors,polynomials,zinc,locally decodable code,interpolation,reed muller code,encoding,error rate,reed muller codes,codeword | Locally decodable code,Discrete mathematics,Hamming code,Combinatorics,Parity-check matrix,Computer science,Block code,Expander code,Linear code,Reed–Muller code,Tornado code | Journal |
Volume | Issue | ISSN |
40 | 4 | 0272-5428 |
ISBN | Citations | PageRank |
978-1-4244-8525-3 | 20 | 0.87 |
References | Authors | |
37 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeev Dvir | 1 | 437 | 30.85 |
| Parikshit Gopalan | 2 | 1186 | 61.52 |
| Sergey Yekhanin | 3 | 983 | 52.33 |