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.

In the classical “Bits Through Queues” paper, it was hypothesized that full feedback always increases the capacity of first-in-first-out queues, except when the service time distribution is memoryless. More recently, a non-explicit sufficient condition under which feedback increases capacity was provided, along with simple examples of service times meeting this condition. While this condition yields examples where feedback is beneficial, it does not offer explicit structural properties of such service times. In this paper, we show that full feedback increases capacity whenever the service time has bounded support. This is achieved by investigating a generalized notion of feedback, with full feedback and weak feedback as particular cases.

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.

In their "Bits Through Queues" paper, Anantharam and Verdú showed that if the service time is memoryless feedback does not increase capacity under a FIFO policy, and further conjectured that feedback increases capacity for all other service times. Towards this conjecture, a recent paper by Aptel and Tchamkerten provided a sufficient condition on the service time under which feedback increases capacity. While this condition yields examples of service times for which feedback is helpful, it does not provide explicit structural properties of such service times.In this paper, we consider the discrete-time setting and show that feedback increases capacity for any service time with finite support. We also show that the above sufficient condition is inconclusive for service times with infinite support.

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.

Consider the compressed sensing setup where the support$\mathbf {s}^{\ast}$of an$m$-sparse$d$-dimensional signal$\mathbf {x}$is to be recovered from$n$linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate$\mathbf {s}_{\text {in}}$of the true support$\mathbf {s}^{\ast}$, and outputs a refined support estimate$\mathbf {s}_{\text {out}}$. We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is$\mathbf {s}_{\text {out}}\supseteq \mathbf {s}^{\ast} $. These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in$m$number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is${\mathcal{O}}(m n d)$. Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE’s support recovery performance lies between OMP and BP. These results show that LiRE can be used generically, on top of any suboptimal baseline support recovery algorithm, to improve support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Alternatively, LiRE may be used as a standalone support recovery algorithm that is competitive with respect to OMP.

This article proposes LiRE, a low complexity algorithm designed to efficiently correct errors made by any given baseline compressed sensing support recovery algorithms. LiRE takes as input an estimate$\mathrm{s}_{\text{in}}$of the true support$\mathrm{s}^{\ast}$of an$m$-sparse$d$-dimensional signal x observed through$n$linear measurements, and outputs a refined support estimate$\mathrm{s}_{\text{out}}$of size$m$. Sufficient conditions are established in the noiseless setup under which LiRE recovers all missed true features, i.e.,$\mathrm{s}_{\text{out}}\supseteq \mathrm{s}^{\ast}$. Experimental results with Gaussian design matrices show that LiRE reduces the number of measurements needed for perfect support recovery via CoSaMP, BP, and OMP by up to 15%, 25%, and 40%, respectively, depending on the level of sparsity. Interestingly, adding LiRE to OMP yields a support recovery algorithm that is more accurate and significantly faster than Basis Pursuit. This conclusion carries over in the noisy measurement setup with the combination of LiRE and OMP against LASSO. These results suggest that LiRE may be used generically, on top of any baseline support recovery algorithm, to boost support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Finally, with a random initialization LiRE becomes a standalone algorithm with OMP-like complexity, and whose reconstruction performance lies between OMP and BP.

The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint.

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).

How many neurons are needed to approximate a target probability distribution using a neural network with a given input distribution and approximation error? This paper examines this question for the case when the input distribution is uniform, and the target distribution belongs to the class of histogram distributions. We obtain a new upper bound on the number of required neurons, which is strictly better than previously existing upper bounds. The key ingredient in this improvement is an efficient construction of the neural nets representing piecewise linear functions. We also obtain a lower bound on the minimum number of neurons needed to approximate the histogram distributions.

This paper investigates the classical modulo two sum problem in source coding, but with a common observation: a transmitter observes (X,Z), the other transmitter observes (Y,Z), and the receiver wants to compute X ⊕Y without error. Through a coupling argument, this paper establishes a new lower bound on the sum-rate when X -Z -Y forms a Markov chain.

In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times.

This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength.

The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint.

In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.

The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay-the elapsed time between when information is available at the transmitter and when it is decoded-and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength n, the second-order term in the maximum rate expansion is of order Θ(1/p) for any sampling rate ρ = O(1/√n) (and ρ = ω(1/n) for otherwise reliable communication is impossible). Instead, if ρ = ω(1/√n), then the second-order term is the same as under full sampling and is given by a standard Θ(√n) term. However, if the delay constraint is only slightly relaxed to n(1+o(1)), then the above order transition (for ρ = O(1/√n) and ρ = w(1/√n)) vanishes and the secondorder term remains the same as under full sampling for any ρ = ω(1/n).

The approximation power of general feedforward neural networks with piecewise linear activation functions is investigated. First, lower bounds on the size of a network are established in terms of the approximation error and network depth and width. These bounds improve upon state-of-the-art bounds for certain classes of functions, such as strongly convex functions. Second, an upper bound is established on the difference of two neural networks with identical weights but different activation functions.

In their “Bits Through Queues” paper, Anantharam and Verdu showed that, under FIFO service policy, feedback does not increase the capacity of a queue when the service time is exponentially distributed. Whether this negative and surprising result-since the channel has memory-holds for other combinations of service policies and service times ever since has remained an open question. This paper first provides a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. Underlying this condition is a notion of weak feedback wherein instead of the queue departure times the transmitter is informed about the instants when packets start to be served. Service times that satisfy this condition include a uniformly distributed service time for the continuous-time model and a binary service time for the discrete-time model. Second, a sufficient condition is given under which feedback does not increase capacity. This condition is satisfied, for instance, by queues with Last-Come- First-Served service policies and bounded service times.

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.

The construction of deletion codes for the editing metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of lattices' translates. These lattices, in turn, are obtained from Construction A applied to binary codes and Z4-codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices. For any fixed number of deletions, provided the number of runs is large enough our method supplies a correction technique. For fixed number of runs and binary sequence length large our lattice construction is shown to be tight up to constants.

This paper establishes non-asymptotic tradeoffs between detection delay, output sampling rate, and communication rate for bursty communication. These tradeoffs imply regimes where the gap to capacity is captured by the inverse of the sampling rate rather than the usual dispersion.

This paper establishes the capacity region for a class of source coding function computation setups, where sources of information are available at the nodes of a tree and where a function of these sources must be computed at its root. The capacity region holds for any function as long as the sources' joint distribution satisfies a certain Markov criterion. This criterion is met, in particular, when the sources are independent. This result recovers the capacity regions of several function computation setups. These include the point-to-point communication setting with arbitrary sources, the noiseless multiple access network with conditionally independent sources, and the cascade network with Markovian sources.

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.

The problem of detecting a transient change in distribution of a discrete time series is investigated when there is a constraint on the number of observed samples. Under a minimax setting where the change time is unknown, the objective is to design a statistical test that minimizes a measure of worst case delay under a constraint on the average time to false alarm as well as a constraint on the sampling rate. Leveraging the results in the non-transient setting, it is shown that under full sampling there exists an asymptotic threshold on the minimum duration of a change that can be detected reliably with such false alarm constrained tests. Next, given a transient change with duration above this asymptotic threshold, the smallest sampling rate for which the change can be detected as efficiently as under full sampling is characterized asymptotically.

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.

Insertion/Deletion codes for the Levenshtein distance are constructed by truncation of lattices for the L1metric. These lattices are obtained from Construction A applied to binary codes and Z4-codes. Finally, Gilbert and Hamming type of bounds are derived.

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.

This paper investigates a distributed function computation setting where the underlying network is a rooted directed tree and where the root wants to compute a function of the sources of information available at the nodes of the network. The main result provides the rate region for an arbitrary function under the assumption that the sources satisfy a general criterion. This criterion is satisfied, in particular, when the sources are independent.

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.

A receiver wants to compute a function of two correlated sources separately observed by two transmitters. One of the transmitters is allowed to cooperate with the other transmitter by sending it some data before both transmitters convey information to the receiver. Assuming noiseless communication, what is the minimum number of bits that needs to be communicated by each transmitter to the receiver for a given number of cooperation bits? In this paper, first a general inner bound to the above three dimensional rate region is provided and shown to be tight in a number of interesting settings: the function is partially invertible, full cooperation, one-round point-to-point communication, two-round point-to-point communication, and cascade. Second, the related Kaspi-Berger rate distortion problem is investigated where the receiver now wants to recover the sources within some distortion. By using ideas developed for establishing the above inner bound, a new rate distortion inner bound is proposed. This bound always includes the time sharing of Kaspi-Berger's inner bounds and inclusion is strict in certain cases.

A transmitter has access to X, a relay has access to Y, and a receiver has access to Z and wants to compute a given function f(X, Y, Z). How many bits must be transmitted from the transmitter to the relay and from the relay to the receiver so that the latter can reliably recover f(X, Y, Z)? The main result is an inner bound to the rate region of this problem which is tight when X - Y - Z forms a Markov chain.

A Gaussian random walk (or a Wiener process), possibly with drift, is observed in a noisy or delayed fashion. The problem considered in this paper is to estimate the first time$\tau $the random walk reaches a given level. Specifically, the average$p$-moment ($p\geq 1$) optimization problem$\inf _{\eta} {\BBE} \vert \eta -\tau \vert ^{p}$is investigated where the infimum is taken over the set of stopping times that are defined on the observation process. When there is no drift, optimal stopping rules are characterized for both types of observations. When there is a drift, upper and lower bounds on$\inf _{\eta} {\BBE} \vert \eta -\tau \vert ^{p}$are established for both types of observations. The bounds are tight in the large-level regime for noisy observations and in the large-level-large-delay regime for delayed observations. Noteworthy, for noisy observations there exists an asymptotically optimal stopping rule that is a function of a single observation. Simulation results are provided that corroborate the validity of the results for non-asymptotic settings.

Given a Gaussian random walk X with drift, we consider estimating its first-passage time τ, of a given level ℓ, with a stopping time η defined over an observation process Y that is either a noisy version of X, or a delayed version of X. For both cases, we provide lower bounds on average moments E|η - τ|p, p ≥ 1, for any stopping rule η, and exhibit simple stopping rules that achieve these bounds in the large threshold regime and in the large threshold large delay regime, respectively. The results immediately extend to the corresponding continuous time settings where X and Y are standard Wiener processes with drift.

A receiver wants to compute a function f of two correlated sources X and Y and side information Z. What is the minimum number of bits that needs to be communicated by each transmitter? In this paper, we derive inner and outer bounds to the rate region which coincide in the cases where f is partially invertible and where one of the sources is constant. From the former case we recover the Slepian-Wolf rate region.

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.

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.

Motivated by certain recent problems in asynchronous communication, we introduce and study B(n, d, w), defined as the maximum number of length n binary sequences with minimum distance d, and such that each sequence has weight at least w. Specifically, we investigate the asymptotic exponential growth rate of B(n, d, w) with respect to n and with fixed ratios δ = d/n and ω = w/n. For ω ∈ [0, 1/2], this growth rate function b(δ, ω) is shown to be equal to a(δ), the asymptotic exponential growth rate of A(n, d)-the maximum number of length n binary sequences with minimum distance d. For ω ∈ (1/2, 1), we show that b(δ, ω) ≤ a(δ, ω) + f(ω), where a(δ, ω) denotes the asymptotic exponential growth rate of A(n, d, w), the maximum number of length n binary sequences with minimum distance d and constant weight w, and where f(w) is a certain function that satisfies 0ω→1f(ω) = limω→1/2f(ω) = 0. Based on numerical evidence, we conjecture that b(δ, ω) is actually equal to a(δ, ω) for ω ∈ (1/2, 1). Finally, lower bounds on B(n, d, w) are obtained via explicit code constructions.

A novel quickest detection setting is proposed, generalizing the well-known Bayesian change-point detection model. Suppose{(Xi,Yi)}iges 1 is a sequence of pairs of random variables, and thatSis a stopping time with respect to{Xi}iges 1. The problem is to find a stopping timeTwith respect to{Yi}iges 1 that optimally tracksS, in the sense thatTminimizes the expectedreactiondelay\BBE(T-S)+, while keeping thefalse-alarmprobabilityP(Talphaisin[0,1]. This problem formulation applies in several areas, such as in communication, detection, forecasting, and quality control.

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 study a problem of broadcasting confidential messages to multiple receivers under an information-theoretic secrecy constraint. Two scenarios are considered: 1) all receivers are to obtain a common message; and 2) each receiver is to obtain an independent message. Moreover, two models are considered: parallel channels and fast-fading channels. For the case of reversely degraded parallel channels, one eavesdropper, and an arbitrary number of legitimate receivers, we determine the secrecy capacity for transmitting a common message, and the secrecy sum-capacity for transmitting independent messages. For the case of fast-fading channels, we assume that the channel state information of the legitimate receivers is known to all the terminals, while that of the eavesdropper is known only to itself. We show that, using a suitable binning strategy, a common message can be reliably and securely transmitted at a rate independent of the number of receivers. We also show that a simple opportunistic transmission strategy is optimal for the reliable and secure transmission of independent messages in the limit of large number of receivers.

We present a generalization of the well-known Bayesian change-point detection problem. Specifically, let {(Xi,Yi)}iges1be a sequence of pairs of random variables, and let S be a stopping time with respect to {Xi}iges1. We assume that the (Xi, Yi)'s take values in the same finite alphabet X times Y. For a fixed kappa ges 1, we consider the problem of finding a stopping time Ti}iges1that optimally tracks S, in the sense that T minimizes the average reaction time E(T - S)+, while it keeps the false-alarm probability P(Tkappa), and constructs the associated optimal stopping times T. In this paper, we provide a sufficient condition on {(Xi,Yi)}iges1and S under which the algorithm running time is polynomial in kappa, and we illustrate this condition with two examples: a Bayesian change-point problem and a pure tracking stopping time problem.

We study the information theoretic limits of communication over asynchronous discrete memoryless channels. The transmitter starts sending a block codeword of length N at a time v uniformly distributed within the interval [1, 2, ..., L]. We assume that the receiver knows L but not v. We give a scaling law of L with respect to N for which reliable communication can be achieved. Specifically, we propose a communication scheme with the property that, unless the asynchrony level L grows at least as eNC, where C denotes the capacity of the synchronized channel, arbitrary low error probability can be achieved. If L grows sub-exponentially in N, the capacity is the same as that of the ordinary synchronized channel. Further, we provide a lower bound to the error probability given a certain channel, codebook, and asynchrony level. This bound together with our scheme shows that, in certain cases, the condition L les eNC(1-delta)for any delta > 0 is an asymptotic necessary and sufficient condition for reliable communication. Finally we extend our analysis to a simple scenario where communication is carried over a Gaussian channel with antipodal signaling +radicP and -radicP. We show that a necessary condition on the amount of power needed in order to guarantee reliable communication is that P must scale as 1/NlogL when L rarr infin

Suppose Q is a family of discrete memoryless channels. An unknown member of Q will be available, with perfect, causal output feedback for communication. We study a scenario where communication is carried by first testing the channel by means of a training sequence, then coding according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such coding scheme. If we consider the Binary Symmetric and the Z families of channels this bound is much lower than Burnashev's exponent. For example, in the case of Binary Symmetric Channels this bound has a slope that vanishes at capacity. This is to be compared with our previous result that demonstrates the existence of coding schemes that achieve Burnashev's exponent (that has a nonzero slope at capacity) even though the channel is revealed neither to the transmitter nor to the receiver. Hence, the present result suggests that, in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.

Burnashev in 1976 gave an exact expression for the reliability function of a discrete memoryless channel (DMC) with noiseless feedback. A coding scheme that achieves this exponent needs, in general, to know the statistics of the channel. Suppose now that the coding scheme is designed knowing only that the channel belongs to a family Q of DMCs. Is there a coding scheme with noiseless feedback that achieves Burnashev's exponent uniformly over Q at a nontrivial rate? We answer the question in the affirmative for two families of channels (binary symmetric, and Z). For these families we show that, for any given fraction, there is a feedback coding strategy such that for any member of the family: i) guarantees this fraction of its capacity as rate, and ii) guarantees the corresponding Burnashev's exponent. Therefore, for these families, in terms of delay and error probability, the knowledge of the channel becomes asymptotically irrelevant in feedback code design: there are blind schemes that perform as well as the best coding scheme designed with the foreknowledge of the channel under use. However, a converse result shows that, in general, even for families that consist of only two channels, such blind schemes do not exist.

We consider communication over a time invariant discrete memoryless channel with noiseless and instantaneous feedback. We assume that the communicating parties are not aware of the underlying channel, however they know that it belongs to some specific family of discrete memoryless channels. Recent results (A. Tchamkerten and I.E. Telatar) show that for certain families (e.g., binary symmetric channels and Z channels) there exists coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent

Suppose Q is a family of discrete memoryless channels. An unknown member of Q is available with perfect (causal) feedback for communication. A recent result (A. Tchamkerten and I.E. Telatar) shows the existence, for certain families of channels (e.g. binary symmetric channels and Z channels), of coding schemes that achieve Burnashev's exponent universally over these families. In other words, in certain cases, there is no loss in the error exponent by ignoring the channel: transmitter and receiver can design optimal blind coding schemes that perform as well as the best feedback coding schemes tuned for the channel under use. Here we study the situation where communication is carried by first testing the channel by means of a training sequence, then coding the information according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such scheme. If we consider binary symmetric channels and Z channels this bound is much lower than Burnashev's exponent. This suggests that in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.

We consider communication over a time-invariant discrete memoryless channel (DMC) with noiseless and instantaneous feedback. We assume that the transmitter and the receiver are not aware of the underlying channel, however, they know that it belongs to some specific family of DMCs. Recent results show that for certain families (e.g., binary-symmetric channels and Z channels) there exist coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent.

Communication over unknown discrete memoryless channels with instantaneous and perfect feedback is considered. For a given set of channels we define a notion of optimal coding schemes in terms of achievable rate and error exponent, and prove the existence of such coding schemes for two families of channels

We consider a scalar additive channel x /spl rarr/ x + N whose input is amplitude constrained. By extending Smith's (1969) argument, we derive a sufficient condition on noise probability density functions (pdf) that guarantee finite support for the associated capacity-achieving distribution(s).