Matching vector codes

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

A locally decodable code encodes a message by a codeword, such that even if the codeword is corrupted by noise, each message bit can be recovered with high probability by a randomized decoding procedure that reads only few bits of the codeword. 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. In this work we develop a new view of MV codes and uncover certain similarities between them and classical Reed Muller codes. Our view allows us to obtain a deeper insight into the power and limitations of MV codes. We use it to construct codes that can tolerate more errors or are shorter than previously known codes for certain parameter settings.We also show super-linear lower bounds on the codeword length of any MV code.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages705-714
Number of pages10
DOIs
StatePublished - Dec 1 2010
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Locally decodable codes
  • Matching vectors
  • Reed Muller codes

Fingerprint Dive into the research topics of 'Matching vector codes'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., Gopalan, P., & Yekhanin, S. (2010). Matching vector codes. In Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 (pp. 705-714). [5671335] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2010.73