We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining @math , the zero-rate threshold of adversarial deletions, defined to be the supremum of all @math for which there exists a code family with rate bounded away from 0 capable of correcting a fraction @math of adversarial deletions. A recent construction of deletion-correcting codes [ 17] shows that @math , and the trivial upper bound, @math , is the best known. Perhaps surprisingly, we do not know whether or not @math . In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of @math deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction @math of oblivious deletions, establishing that the associated zero-rate threshold @math equals @math . For online deletions, where the channel decides whether to delete bit @math based only on knowledge of bits @math , define the deterministic zero-rate threshold for online deletions @math to be the supremum of @math for which there exist deterministic codes against an online channel causing @math deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove @math if and only if @math .
To the best of our knowledge, ours is the first work to address both oblivious and online deletions. We feel that given the large gaps in our understanding of coding against adversarial deletions, and the potential of taking advantage of less stringent models of deletion exhibited in this work, further study of these models seems timely and important. In particular, for online deletions as well, the zero-rate threshold is between @math and @math . It is an interesting challenge to ascertain if one can take advantage of the online restriction, and push some of the ideas in @cite_7 and this work, to enable decoding a fraction of online deletions approaching @math .
@cite_7
2952657341 2964292545 2034381439 2133470506
We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed @math , we construct a family of codes over alphabet of size @math with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching @math . In particular, for binary codes, we are able to recover a fraction of deletions approaching @math . Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was @math , and around @math for the binary case. Our result pins down the largest fraction of correctable deletions for @math -ary codes as @math , since @math is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between @math and @math for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question. We consider the problem of clustering a graph @math into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables @math , where @math is the incidence matrix of a graph @math , @math is the vector of unknown vertex variables (with a uniform prior), and @math is a noise vector with Bernoulli @math i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of @math is possible if and only the graph @math is connected, with a sharp threshold at the edge probability @math for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability @math needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by @math , it is shown that exact recovery is possible if and only if @math . In other words, @math is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph @math , defining the degree rate as @math , where @math is the minimum degree of the graph, it is shown that the proposed method achieves the rate @math , where @math is the spectral gap of the graph @math . The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1 2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1 2) process. Our results show that this is indeed the case. The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting “nature's secret”, that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.