Correctness and Corruption of Locally Decodable Codes

Correctness and Corruption of Locally Decodable Codes. Cheraghchi, M., Gál, A., & Mills, A. 2012. Manuscript.

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the decoding procedures. We refer to the probability of returning the correct answer as the \em correctness of the decoding algorithm. Thus far, the study of LDCs has focused on the question of the tradeoff between their length and the query complexity of the decoders. Another natural question is what is the largest possible correctness, as a function of the amount of codeword corruption and the number of queries, regardless of the length of the codewords. Goldreich et al. (Computational Complexity 15(3), 2006) observed that for a given number of queries and fraction of errors, the correctness probability cannot be arbitrarily close to $1$. However, the quantitative dependence between the largest possible correctness and the amount of corruption $δ$ has not been established before. We present several bounds on the largest possible correctness for LDCs, as a function of the amount of corruption tolerated and the number of queries used, regardless of the length of the code. Our bounds are close to tight. We also investigate the relationship between the amount of corruption tolerated by an LDC and its minimum distance as an error correcting code. Even though intuitively the two notions are expected to be related, we demonstrate that in general this is not the case. However, we show a close relationship between minimum distance and amount of corruption tolerated for linear codes over arbitrary finite fields, and for binary nonlinear codes. We use these results to strengthen the known bounds on the largest possible amount of corruption that can be tolerated by LDCs (with any nontrivial correctness better than random guessing) regardless of the query complexity or the length of the code.

@UNPUBLISHED{ref:CGM12,
  author =	 {Mahdi Cheraghchi and Anna G\'al and Andrew Mills},
  title =	 {Correctness and Corruption of Locally Decodable
                  Codes},
  year =	 2012,
  url_Paper =	 {https://eccc.weizmann.ac.il//report/2012/172/},
  abstract =	 {Locally decodable codes (LDCs) are error correcting
                  codes with the extra property that it is sufficient
                  to read just a small number of positions of a
                  possibly corrupted codeword in order to recover any
                  one position of the input.  To achieve this, it is
                  necessary to use randomness in the decoding
                  procedures.  We refer to the probability of
                  returning the correct answer as the {\em
                  correctness} of the decoding algorithm.  Thus far,
                  the study of LDCs has focused on the question of the
                  tradeoff between their length and the query
                  complexity of the decoders.  Another natural
                  question is what is the largest possible
                  correctness, as a function of the amount of codeword
                  corruption and the number of queries, regardless of
                  the length of the codewords.  Goldreich et
                  al. (Computational Complexity 15(3), 2006) observed
                  that for a given number of queries and fraction of
                  errors, the correctness probability cannot be
                  arbitrarily close to $1$.  However, the quantitative
                  dependence between the largest possible correctness
                  and the amount of corruption $\delta$ has not been
                  established before.  We present several bounds on
                  the largest possible correctness for LDCs, as a
                  function of the amount of corruption tolerated and
                  the number of queries used, regardless of the length
                  of the code.  Our bounds are close to tight.  We
                  also investigate the relationship between the amount
                  of corruption tolerated by an LDC and its minimum
                  distance as an error correcting code.  Even though
                  intuitively the two notions are expected to be
                  related, we demonstrate that in general this is not
                  the case.  However, we show a close relationship
                  between minimum distance and amount of corruption
                  tolerated for linear codes over arbitrary finite
                  fields, and for binary nonlinear codes.  We use
                  these results to strengthen the known bounds on the
                  largest possible amount of corruption that can be
                  tolerated by LDCs (with any nontrivial correctness
                  better than random guessing) regardless of the query
                  complexity or the length of the code.  },
  note =	 {Manuscript.}
}

Downloads: 0