Publications

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 corrupted by substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, pre- senting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses O(n N) field operations, where n is the codeword length.

In this work we consider a generalization of the well-studied problem of coding for “stuck-at” errors, which we refer to as “strong stuck-at” codes. In the traditional framework of stuck-at codes, the task involves encoding a message into a one-dimensional binary vector. However, a certain number of the bits in this vector are `frozen’, meaning they are fixed at a predetermined value and cannot be altered by the encoder. The decoder, aware of the proportion of frozen bits but not their specific positions, is responsible for deciphering the intended message. We consider a more challenging version of this problem where the decoder does not even know the fraction of frozen bits. We construct explicit and efficient encoding and decoding algorithms that get arbitrarily close to capacity in this scenario. Furthermore, to the best of our knowledge, our construction is the first fully explicit construction of stuck-at codes that approaches capacity.