The Taub Faculty of Computer Science Events and Talks

Binary and q-ary sequences have always been used in communication channel as the carrier or the vessel of information. In order to establish an efficient and error-free communication channel, investigations on the properties of sequences are crucial. The property that we will investigate in this seminar is the reconstruction capability of binary sequences in particular from its subsequences. This is called the Sequence Reconstruction Problem. The problem considers a communication scenario where the sender transmits a sequence from some codebook and the receiver obtains multiple noisy reads of the original sequence. Noisy reads here refer to possibly erroneous copies of the original sequence. The receiver/decoder then aims to reconstruct the original sequence from these noisy reads. The error that we consider in this seminar is only deletion error where some elements of the original sequence might be deleted. Thus, the noisy reads here are in the form of subsequences of the original sequence. In this seminar, we assume that the decoder only receives some fixed number of noisy reads. In other words, the decoder receives a fixed number of subsequences. In this case, we also assume that all received noisy reads are distinct. We construct codes that are capable of correcting t deletions with multiple noisy reads. Special attention is given to the case when t=1 and t=2. In particular, we show that a Constrained Shifted VT code achieves asymptotically optimal redundancy of in a single-deletion channel given that the decoder retrieves two distinct noisy reads. Also, we provide an explicit two-deletion reconstruction code that can reconstruct the original sequence with 5 noisy reads with 2 log n + o(log n) redundancy.