Algebraic and Combinatorial Coding Theory
Combinatorial Coding Theory I

Uncertainty of Reconstructing Multiple Messages from Uniform-Tandem-Duplication Noise

Yonatan Yehezkeally, Moshe Schwartz

Date & Time

01:00 am – 01:00 am


We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with $m>2$ strings (where a previous paper considered $m=2$) in asymptotic terms, where code-words are taken from a typical set of strings, consisting a growing fraction of the space size, converging to $1$. Thus, we find the trade-off between the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease the required number of reads.


Yonatan Yehezkeally

Ben-Gurion University of the Negev

Moshe Schwartz

Ben-Gurion University of the Negev

Session Chair

Navin Kashyap

Indian Institute of Science