It is shown that a memoryless source can be compressed arbitrarily close to its entropy rate while guaranteeing the private local decoding of any source symbol. This is achieved through a remarkably simple compression scheme that effectively separates compression and privacy.

A fixed-length compression scheme is said to be locally decodable if any bit of the source sequence can be recovered by probing only a small subset of the compressed bits. A recent work addressed the problem of private locally decodable compression: Is it possible to compress a source$X^{n}$such that the compressed bits probed by the local decoder to recover any$X_{i}$reveal no information about the remainder of the source sequence$\{X_{j}:j\neq i\}$? A compression scheme was proposed that achieved a non-trivial rate and private local decoding, but it remained unclear whether the gap to entropy was inherent to the privacy property or not. We show that private local decodability is not a fundamental impediment to compression, and prove the existence of an entropy-achieving compression scheme for i.i.d. bit strings that guarantees the private local decodability of any individual source symbol.

Classical compression schemes suggest that message symbols cannot be privately decoded; if a string Xnis encoded into a codeword CnRat a non-trivial rate R, then the decoding of an individual symbol Xireveals information about the rest of the symbols Xn\Xi.While this holds for virtually all lossless compression schemes, it is shown that this need not be the case. This paper proposes a lossless compression scheme for bit strings with the following properties. For any sufficiently small p > 0, it encodes each length-n bit string of Hamming weight at most np into a binary codeword of length $O\left( {np{{\log }^2}\frac{1}{p}} \right)$ such that the subset of compressed bits that need to be probed in order to decode a particular message bit reveals no additional information about the other message bits.

This paper investigates the Slepian-Wolf distributed compression of two sources Xnand Ynwith the additional property that any pair (Xi, Yi) should reliably be decoded by probing a small number d of compressed bits. We show that for certain source distributions, the error probability of any such local decoder is lower bounded by 2–O(d), in the worst case over index i, whenever one of the sources is compressed below its entropy. Unlike the single-source setup, it is thus impossible to simultaneously achieve constant local decodability d and vanishing local decoding error probability as n increases. We also provide a compression scheme with a local decoder that almost achieves the above lower bound.

This paper addresses the problem of data compression with local decoding and local update. A compression scheme has worst-case local decoding dwcif any bit of the raw file can be recovered by probing at most dwcbits of the compressed sequence, and has update efficiency of uwcif a single bit of the raw file can be updated by modifying at most uwcbits of the compressed sequence. This article provides an entropy-achieving compression scheme for memoryless sources that simultaneously achieves O (log log n) local decoding and update efficiency. Key to this achievability result is a novel succinct data structure for sparse sequences which allows efficient local decoding and local update. Under general assumptions on the local decoder and update algorithms, a converse result shows that the maximum of dwcand uwcmust grow as Ω(log log n).

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information was recently derived for bursty communication when information is available infrequently at random times at the transmitter. Furthermore, it was shown that even if the receiver is constrained to sample only a fraction ρ ∈ (0, 1] of the channel outputs, there is no capacity penalty. That is, for any strictly positive sampling rate ρ, the asynchronous capacity per unit cost is the same as under full sampling, i.e., when ρ = 1. Moreover, there is no penalty in terms of decoding delay. These results are asymptotic in nature, considering the limit as the number B of bits to be transmitted tends to infinity, while the sampling rate ρ remains fixed. A natural question is then whether the sampling rate ρ(B) can drop to zero without introducing a capacity (or delay) penalty compared with full sampling. We answer this question affirmatively. The main result of this paper is an essentially tight characterization of the minimum sampling rate. We show that any sampling rate that grows at least as fast as ω(1/B) is achievable, while any sampling rate smaller than o(1/B) yields unreliable communication. The key ingredient in our improved achievability result is a new, multi-phase adaptive sampling scheme for locating transient changes, which we believe may be of independent interest for certain change-point detection problems.

In a recently proposed asynchronous communication setup, the receiver observes mostly pure background noise except for a brief and a priori unknown period of time when data is transmitted. Capacity per unit cost and minimum communication delay were characterized and shown to be unaffected by a sparse sampling at the receiver as long as the number of samples represents a constant fraction of the total channel outputs.

Source coding is concerned with optimally compressing data, so that it can be reconstructed up to a specified distortion from its compressed representation. Usually, in fixed-length compression, a sequence of n symbols (from some alphabet) is encoded to a sequence of k symbols (bits). The decoder produces an estimate of the original sequence of n symbols from the encoded bits. The rate-distortion function characterizes the optimal possible rate of compression allowing a given distortion in reconstruction as n grows. This function depends on the source probability distribution. In a locally recoverable decoding, to reconstruct a single symbol, only a few compressed bits are accessed. In this paper we find the limits of local recovery for rates near the rate-distortion function. For a wide set of source distributions, we show that, it is possible to compress within ε of the rate-distortion function such the local recoverability grows as Ω(log(1/ε)); that is, in order to recover one source symbol, at least Ω(log(1/ε)) bits of the compressed symbols are queried. We also show order optimal impossibility results. Similar results are provided for lossless source coding as well.

Motivated by distributed storage applications, we investigate the degree to which capacity achieving codes can be efficiently updated when a single information symbol changes, and the degree to which such codes can be efficiently repaired when a single encoded symbol is lost. Specifically, we first develop conditions under which optimum error-correction and update-efficiency are possible. We establish that the number of encoded bits that should change in response to a change in a single information bit must scale logarithmically in the block-length of the code, if we are to achieve any nontrivial rate with vanishing probability of error over the binary erasure or binary symmetric channels. Moreover, we show that there exist capacity-achieving codes with this scaling. With respect to local repairability, we develop tight upper and lower bounds on the number of remaining encoded bits that are needed to recover a single lost encoded bit. In particular, we show that when the rate of an optimal code is ε below capacity, the maximum number of codeword symbols required to recover one lost symbol must scale as log1/ε. Several variations on-and extensions of-these results are also developed, including to the problem of rate-distortion coding.

The minimum energy, and, more generally, the minimum cost, to transmit 1 bit of information was recently derived for bursty communication when the information is available infrequently at random times at the transmitter. This result assumes that the receiver is always in the listening mode and samples all channel outputs until it makes a decision. Since sampling is in practice one of the receiver's most energy consuming functions, a natural question is to evaluate capacity per unit cost when the receiver is sampling constrained. This paper investigates such a setting where the receiver can sample only a given fraction ρ ∈ (0, 1] of the channel outputs. It is shown that regardless of ρ > 0, the asynchronous capacity per unit cost is the same as under full sampling, i.e., when ρ = 1. Moreover, a sparse output sampling does not even impact decoding delay-the elapsed time between when information is available and when it is decoded. Hence, surprisingly, it suffices to sample an arbitrarily small fraction of the channel outputs and yet achieve the same (asymptotic) performance as under full output sampling.

The minimum energy, and, more generally, the minimum input cost, to transmit one bit of information has been recently derived for bursty communication when information is available infrequently at random times at the transmitter. This result assumes that the receiver can sample at no cost all channel outputs. Suppose now there is a cost associated to output sampling and that the receiver is constrained to observe only a fraction ρ ϵ (0, 1] of all channel outputs. What is the input cost penalty due to sparse output sampling? Remarkably, there is no penalty: regardless of ρ > 0 the asynchronous capacity per unit cost is the same as under full sampling, i.e., when ρ = 1. Moreover, there is no penalty in terms of decoding delay with respect to full sampling. This latter result relies on the possibility to sample adaptively; the next sample is a function of past samples. When sampling is non-adaptive it is possible to achieve the full sampling asynchronous capacity per unit cost, but the decoding delay gets multiplied by 1/ρ. Therefore adaptive sampling strategies are of particular interest in the very sparse sampling regime.

Secret key extraction, the task of extracting a secret key from shared information that is partially known by an eavesdropper, has important applications in cryptography. Motivated by the requirements of high-speed quantum key distribution, we study secret-key extraction methods with simple and efficient hardware implementations, in particular, linear transformations based on low-density random matrices. We show that this method can achieve the information-theoretic upper bound (conditional Shannon entropy) on efficiency for a wide range of key-distribution systems. In addition, we introduce a numerical method that allows us to tightly estimate the quality of the generated secret key in the regime of finite block length, and use this method to demonstrate that low-density random matrices achieve very high performance for secret key extraction.

The capacity per unit cost, or, equivalently, the minimum cost to transmit one bit, is a well-studied quantity under the assumption of full synchrony between the transmitter and the receiver. In many applications, such as sensor networks, transmissions are very bursty, with amounts of bits arriving infrequently at random times. In such scenarios, the cost of acquiring synchronization is significant and one is interested in the fundamental limits on communication without assuming a priori synchronization. In this paper, the minimum cost to transmitBbits of information asynchronously is shown to be equal to (B +H̅)ksync, whereksyncis the synchronous minimum cost per bit and H̅ is a measure of timing uncertainty equal to the entropy for most reasonable arrival time distributions. This result holds when the transmitter can stay idle at no cost and is a particular case of a general result which holds for arbitrary cost functions.

Several aspects of the problem of asynchronous point-to-point communication without feedback are developed when the source is highly intermittent. In the system model of interest, the codeword is transmitted at a random time within a prescribed window whose length corresponds to the level of asynchronism between the transmitter and the receiver. The decoder operates sequentially and communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. For such systems, general upper and lower bounds on capacity as a function of the level of asynchronism are established, and are shown to coincide in some nontrivial cases. From these bounds, several properties of this asynchronous capacity are derived. In addition, the performance of training-based schemes is investigated. It is shown that such schemes, which implement synchronization and information transmission on separate degrees of freedom in the encoding, cannot achieve the asynchronous capacity in general, and that the penalty is particularly significant in the high-rate regime.

An update efficient code is a mapping from messages to codewords such that small perturbations in the message induce only slight changes to the corresponding codeword. The parameter that captures this notion is called update-efficiency. In this paper we study update-efficient error-correcting codes and develop their basic properties. While update-efficiency and error-correction are two conflicting objectives, we deduce conditions for existence of such codes. In particular, logarithmically growing update-efficiency is achievable with a capacity-achieving linear code in both binary symmetric and binary erasure channels. On the other hand we show a tight converse result. Our result implies that it is not possible to have a capacity-achieving code in binary symmetric channel that has sub-logarithmic update-efficiency. This is true in the case of the binary erasure channel as well for linear codes. We also discuss a number of questions related to update-efficient adversarial error-correcting codes.

Single-message unequal error protection (UEP) is a channel coding scheme that protects one special message differently from other (regular) messages. This induces three different types of errors in the system: 1) miss (where we decode the special codeword as a regular codeword), 2) false alarm (where we decode a regular codeword as the special codeword), and 3) decoding error (where we decode a regular codeword to another regular codeword). In this paper, we investigate the fundamental limits of single-message UEP, in the context of discrete memoryless channels (DMCs) without feedback. Similar to Borade et al., we use error exponents as the performance metric, and discuss maximizing the miss error exponent and the false alarm error exponent, respectively. We provide a new converse proof for the miss reliability function, i.e., the optimal miss error exponent as a function of communication rate, and extend the inner and outer bound results for the false alarm reliability function in Borade et al. from rates close to capacity to all rates up to capacity.

Based on recent work on asynchronous communication, this paper proposes a slotted asynchronous channel model and investigates the fundamental limits of asynchronous communication, in terms of miss and false alarm error exponents. We propose coding schemes that are suitable for various asynchronous communication scenarios, and quantify more precisely the suboptimality of training-based schemes, i.e., communication strategies that separate synchronization from information transmission. In particular, we show that under a broad set of conditions, training-based schemes are suboptimal at all positive rates. Finally, we demonstrate these performance differences by specializing our results to BSCs and AWGN channels.

The maximum size of a binary code is studied as a function of its lengthn, minimum distanced, and minimum codeword weight \ssiw. This functionB(n,d,w) is first characterized in terms of its exponential growth rate in the limitn→∞ for fixed δ =d/nand ω =w/n. The exponential growth rate ofB(n,d,w) is shown to be equal to the exponential growth rate ofA(n,d) for 0 ≤ ω ≤ 1/2, and equal to the exponential growth rate ofA(n,d,w) for 1/2B(n,d,w) are derived using the semidefinite programming (SDP) method. These bounds yield a nonasymptotic improvement of the second Johnson bound and are tight for certain values of the parameters.

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A ∈ {0, 1}m×n. We establish that when A corresponds to the adjacency matrix of a bipartite graph with sufficient expansion, a simple message-passing algorithm produces an estimate x^ of x satisfying ∥x-x^∥1≤ O(n/k) ∥x-x(k)∥1, where x(k)is the best k-sparse approximation of x. The algorithm performs O(n(log(n/k))2log (k)) computation in total, and the number of measurements required is m = O(k log(n/k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n/k) log(k)). Ultimately, this work is a further step in the direction of more formally developing the broader role of message-passing algorithms in solving compressed sensing problems.

The capacity per unit cost, or equivalently minimum cost to transmit one bit, is a well-studied quantity. It has been studied under the assumption of full synchrony between the transmitter and the receiver. In many applications, such as sensor networks, transmissions are very bursty, with small amounts of bits arriving infrequently at random times. In such scenarios, the cost of acquiring synchronization is significant and one is interested in the fundamental limits on communication without assuming a priori synchronization. In this paper, we show that the minimum cost to transmit B bits of information asynchronously is (B + H̅)ksync, where ksyncis the synchronous minimum cost per bit and H̅ is a measure of timing uncertainty equalling to the entropy for most reasonable arrival time distributions.

A formulation of the problem of asynchronous point-to-point communication is developed. In the system model of interest, the message codeword is transmitted over a channel starting at a randomly chosen time within a prescribed window. The length of the window scales exponentially with the codeword length, where the scaling parameter is referred to as the asynchronism exponent. The receiver knows the transmission window, but not the transmission time. Communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. Under this model, several aspects of the achievable tradeoff between the rate of reliable communication and the asynchronism exponent are quantified. First, the use of generalized constant-composition codebooks and sequential decoding is shown to be sufficient for achieving reliable communication under strictly positive asynchronism exponents at all rates less than the capacity of the synchronized channel. Second, the largest asynchronism exponent under which reliable communication is possible, regardless of rate, is characterized. In contrast to traditional communication architectures, there is no separate synchronization phase in the coding scheme. Rather, synchronization and communication are implemented jointly. The results are relevant to a variety of sensor network and other applications in which intermittent communication is involved.

We consider asynchronous communication over discrete memoryless channels. The transmitter starts sending one block codeword of length N at an instant that is uniformly distributed within a certain time period A, which represents the level of asynchronism between the transmitter and the receiver. The receiver, by means of a sequential decoder, must isolate the message without knowing when the codeword transmission starts but being cognizant of the asynchronism level. Motivated by certain monitoring type of applications, we are interested in communication strategies that 1) operate with short codeword length with respect to the asynchronism level and 2) that guarantee quick decoding. In a recent work the authors showed that the communication rate - defined with respect to the decoder's reaction delay to the sent message - can be strictly positive unlessAgrows faster than lscrNaand alpha exceeding the synchronization threshold. The present work focuses on the regime where a is smaller than thesynchronizationthreshold. The main contribution consists of simple expressions that give upper and lower bounds on the highest achievable rate for any alpha below the synchronization threshold. For random code constructions these bounds are tight.

We consider the “one-shot frame synchronization problem,” where a decoder wants to locate a sync pattern at the output of a memoryless channel on the basis of sequential observations. The sync pattern of length$N$starts being emitted at a random time within some interval of size$A$, where$A$characterizes the asynchronism level. We show that a sequential decoder can optimally locate the sync pattern, i.e., exactly, without delay, and with probability approaching one as$N \rightarrow \infty$, if the asynchronism level grows as$O(e^{N\alpha})$, with$\alpha$below thesynchronization threshold, a constant that admits a simple expression depending on the channel. If$\alpha$exceeds the synchronization threshold, any decoder, sequential or nonsequential, locates the sync pattern with an error that tends to one as$N\rightarrow \infty$. Hence, a sequential decoder can locate a sync pattern as well as the (nonsequential) maximum-likelihood decoder that operates on the basis of output sequences of maximum length$A+N-1$, but with far fewer observations.

We show that linear complexity capacity-approaching information embedding codes exist for information embedding problems. Specifically, we introduce the double-erasure information embedding channel model, and show that in at least some parameter regimes one can achieve rates arbitrarily close to capacity using suitably defined codes on graphs. Furthermore, we show that both encoding and decoding can be implemented with linear complexity by exploiting belief propagation techniques