An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes
<|reference_start|>An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes: The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains $N$ noisy outputs of the codeword. We study the problem of efficient reconstruction using $N$ outputs that are each corrupted by at most $t$ substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses $\mathcal{O}(nN)$ field operations, where $n$ is the codeword length.<|reference_end|>
@article{singhvi2024an,
    title={An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes},
    author={Shubhransh Singhvi, Roni Con, Han Mao Kiah and Eitan Yaakobi},
    journal={arXiv preprint arXiv:2403.07754},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.07754},
    primaryClass={cs.IT math.IT}
}