Paper 2014/260

Locally Decodable Codes for edit distance

Rafail Ostrovsky and Anat Paskin-Cherniavsky

Abstract

Locally decodable codes (LDC)~\cite{BFLS91,KT00} are error correcting codes that allow decoding (any) individual symbol of the message, by reading only few symbols of the codeword. Consider an application such as storage solutions for large data, where errors may occur in the disks (or some disks may just crush). In such an application, it is often desirable to recover only small portions of the data (have random access). Thus, in such applications, using LDC provides enormous efficiency gains over standard error correcting codes (ECCs), that need to read the entire encoded message to learn even a single bit of information. Typically, LDC's, as well as standard ECC's decode the encoded messaged if upto some bounded fraction of the symbols had been modified. This corresponds to decoding strings of bounded Hamming distance from a valid codeword. An often more realistic metric is the edit distance, measuring the shortest sequence of insertions and deletions (indel.) of symbols leading from one word to another. For example, (few) indel. modifications is a more realistic model for mutations occurring in a genome. Even more commonly, communication over the web may sustain deletions (lost packets) and insertions (noise).\footnote{Edit distance is indeed "more expressive" then Hamming distance in the sense that $dist_E(x,y)\leq 2dist_H(x,y)$ always holds, while edit distance 2 may translate to Hamming distance $n$. For instance, consider $x=1010\ldots 10,y=0101\ldots 1$. } Standard ECC's for edit distance have been previously considered~\cite{SZ97}. Furthermore,~\cite{SZ97} devised codes with rate and distance (error tolerance) optimal upto constants. LDC's, originally considered in the setting of PCP's~\cite{BFLS91}, have found many additional applications, and generated a lot of fascinating work (see~\cite{Yek11} and references within). However, combining these two useful settings of LDC, and robustness against indel. errors has never been considered. In this work, we study the question of constructing LDC's for edit distance. We demonstrate a strong positive result - LDC's for edit distance can be achieved, with similar parameters to LDC's for Hamming distance. More precisely, we devise a generic transformation from LDC for Hamming distance to LDC for edit distance with related parameters.

Note: list grants & funding