Matching Vector Codes - Dvir, Zeev; Gopalan, Parikshit; Yekhanin, Sergey (FOCS 2010, 2010)
Starting with the work of Yekhanin, a new family of locally decodable codes based on vectors with restricted dot products has been discovered. We refer to such codes as Matching Vector Codes. In this work, we present a new "polynomial" view of these codes, which uncovers certain similarities to the classical Reed Muller codes. We use this to give decoding algorithms for such codes that can correct a constant fraction of errors. We also present lower bounds on the length of any such code.