Matching Vector Codes

FOCS 2010 |

Published by IEEE

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.