Matching Vector Codes

Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin

Abstract

Starting with the work of Yekhanin, a new family of locally decodable codes based on vectors with restricted dot products has been discovred. 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.

Details

Publication typeInproceedings
Published inFOCS 2010
PublisherIEEE
> Publications > Matching Vector Codes