Matching Vector Codes

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.

Authors

• Zeev Dvir
• Parikshit Gopalan
• Sergey Yekhanin

Keywords

• Decoding
• Polynomials
• Encoding
• Zinc
• Complexity theory
• Interpolation
• Vectors
• Code Vector
• Matching Vector
• Lower Bound
• Dot Product
• Decoding Procedure
• Codeword Length
• Upper Bound
• Complex Numbers
• Hyperplane
• Characteristic Zero
• Amount Of Noise
• Binary Code
• Forward Error Correction
• Linear Algebra
• Finite Field
• Nondecreasing Function
• Polynomial Interpolation
• Code Construction
• Large Amount Of Noise
• Prime Power
• Fractional Error
• Invertible Elements
• Decoding Algorithm
• Canonical Set
• locally decodable codes
• matching vectors
• Reed Muller codes