Search

The entropy of a random variable is well-known to equal the exponential growth rate of the volumes of its typical sets. In this paper, we show that for any log-concave random variable X , the sequence of the \lfloor n\theta \rfloor ^{\text {th}} intrinsic volumes of the typical sets of X in dimensions n \geq 1 grows exponentially with a well-defined rate. We denote this rate by h_{X}(\theta ) , and call it the \theta ^{\text {th}} intrinsic entropy of X . We show that h_{X}(\theta ) is a continuous function of \theta $ over the range [0, 1], thereby providing a smooth interpolation between the values 0 and $h(X)$ at the endpoints 0 and 1, respectively. [ABSTRACT FROM PUBLISHER]

This paper gives upper and lower bounds on the minimum error probability of Bayesian $M$ -ary hypothesis testing in terms of the Arimoto–Rényi conditional entropy of an arbitrary order $\alpha $ . The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ( $\alpha =1$ ) is demonstrated. In particular, in the case where $M$ is finite, we show how to generalize Fano’s inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano’s inequality, allowing $M$ to be infinite, a lower bound on the Arimoto–Rényi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto–Rényi conditional entropy for both positive and negative $\alpha $ . Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto–Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random-coding ensemble. [ABSTRACT FROM PUBLISHER]

Over the past few years, a family of interesting new inequalities for the entropies of sums and differences of random variables has been developed by Ruzsa, Tao, and others, motivated by analogous results in additive combinatorics. This paper extends these earlier results to the case of random variables taking values in \mathbb R^n or, more generally, in arbitrary locally compact and Polish abelian groups. We isolate and study a key quantity, the Ruzsa divergence between two probability distributions, and we show that its properties can be used to extend the earlier inequalities to the present general setting. The new results established include several variations on the theme that the entropies of the sum and the difference of two independent random variables severely constrain each other. Although the setting is quite general, the results are already of interest (and new) for random vectors in \mathbb R^n . In that special case, we discuss quantitative bounds for the stability of the equality conditions in the entropy power inequality, a reverse entropy power inequality for log-concave random vectors, an information-theoretic analog of the Rogers–Shephard inequality for convex bodies, and consequences of some of our results to determinant inequalities for sums of positive-definite matrices. Moreover, by considering various multiplicative subgroups of the complex plane, one obtains new inequalities for the differential entropies of products and ratios of nonzero, complex-valued random variables. [ABSTRACT FROM PUBLISHER]

In this paper, we show that the conditional expectation operators corresponding to a family of source-channel models, defined by natural exponential families with quadratic variance functions and their conjugate priors, have orthonormal polynomials as singular vectors. These models include the Gaussian channel with Gaussian source, the Poisson channel with gamma source, and the binomial channel with beta source. To derive the singular vectors of these models, we prove and employ the equivalent condition that their conditional moments are strictly degree preserving polynomials. [ABSTRACT FROM AUTHOR]

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an $n $ -cell register, where each cell is either empty or contains a particle of one of $P $ possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a $P $ -ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems. [ABSTRACT FROM AUTHOR]

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings. [ABSTRACT FROM PUBLISHER]

In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper, we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,\epsilon )$ -disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$ -set of defective subjects out of a population of size $N$ with false positive probability of an item at most $\epsilon $ . We establish a new connection between $(t,\epsilon )$ -disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs. [ABSTRACT FROM PUBLISHER]

In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Rényi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the RID of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (corresponding to discrete and continuous distributions) when transformed by a Hadamard matrix. Furthermore, we prove that the polarization pattern of the RID admits a closed form expression and follows exactly the Binary Erasure Channel (BEC) polarization pattern in the discrete setting. We discuss the applications of the RID polarization to Compressed Sensing of i.i.d. sources. In particular, we use the RID polarization to construct a family of deterministic ±1-valued sensing matrices for Compressed Sensing. We run numerical simulations to compare the performance of the resulting matrices with that of the random Gaussian and the random Hadamard matrices. The results indicate that the proposed matrices afford competitive performances, while being explicitly constructed. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a cache aided network in which each user is assumed to have individual caches, while upon users’ requests, an update message is sent through a common link to all users. First, we formulate a general information theoretic setting that represents the database as a discrete memoryless source, and the users’ requests as side information that is available everywhere except at the cache encoder. The decoders’ objective is to recover a function of the source and the side information. By viewing cache aided networks in terms of a general distributed source coding problem and through information theoretic arguments, we present inner and outer bounds on the fundamental tradeoff of cache memory size and update rate. Then, we specialize our general inner and outer bounds to a specific model of content delivery networks: file selection networks, in which the database is a collection of independent equal-size files and each user requests one of the files independently. For file selection networks, we provide an outer bound and two inner bounds (for centralized and decentralized caching strategies). For the case when the user request information is uniformly distributed, we characterize the rate versus cache size tradeoff to within a multiplicative gap of 4. By further extending our arguments to the framework of Maddah-Ali and Niesen, we also establish a new outer bound and two new inner bounds in which it is shown to recover the centralized and decentralized strategies, previously established by Maddah-Ali and Niesen. Finally, in terms of rate versus cache size tradeoff, we improve the previous multiplicative gap of 72 to 4.7 for the average case with uniform requests. [ABSTRACT FROM PUBLISHER]

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretic secure key agreement, commitment, and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive, since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (ISIT’07) presented upper and lower bounds on the OT capacity of generalized erasure channels (GECs) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and, therefore, the OT capacity was determined. It was later proved by Pinto et al. [IEEE Trans. Inf. Theory 57(8)] that the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this paper, we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. We obtain our results by a new combination of interactive hashing and typicality tests that are suitable for dealing with the case of low erasure probability ( p^* <1/2 ). [ABSTRACT FROM PUBLISHER]

A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kind of dual conditions. The hyperlogarithmic growth of maximal repetition has been experimentally observed for texts in natural language, whereas the power-law growth of topological entropy implies a vanishing Shannon entropy rate and thus probably does not hold for natural language. In this paper, we provide a constructive example of regular Hilberg processes, which we call random hierarchical association (RHA) processes. Our construction does not apply the standard cutting and stacking method. For the constructed RHA processes, we demonstrate that the expected length of any uniquely decodable code is the orders of magnitude larger than the Shannon block entropy of the ergodic component of the RHA process. Our proposition supplements the classical result by Shields concerning nonexistence of universal redundancy rates. [ABSTRACT FROM PUBLISHER]

We study the channel capacity of a general discrete energy harvesting channel with a finite battery. Contrary to traditional communication systems, the transmitter of such a channel is powered by a device that harvests energy from a random exogenous energy source and has a finite-sized battery. As a consequence, at each transmission opportunity, the system can only transmit a symbol whose energy is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is simultaneously random, instantaneous, and influenced by the full history of the inputs and the energy harvesting process. Furthermore, naturally, in such a channel, the energy information is observed causally at the transmitter. Both of these characteristics pose great challenges for the analysis of the channel capacity. In this paper, we use techniques developed for channels with side information and finite-state channels, to obtain lower and upper bounds on the capacity of energy harvesting channels. In particular, in a general case with Markov energy harvesting processes, we use stationarity and ergodicity theory to compute and optimize the achievable rates for the channels, and derive a series of computable capacity upper and lower bounds. [ABSTRACT FROM AUTHOR]

We consider the problem of detecting abrupt parameter changes in a stochastic regression with unknown noise distribution. The process changes at some unknown point of time. Under general conditions on the regression function and unknown distributions of observations before and after the disruption, the paper develops a nonparametric cumulative sum procedure (CUSUM). Unlike likelihood-based CUSUM algorithms, constructed mostly on log-likelihood ratio statistics, we use a special system of basic statistics in Page’s procedure. By applying a sequential sampling scheme, which measures time in terms of accumulated Kullback–Leibler (K-L) divergence, we come to a system of statistics with the martingale properties close to those of the log-likelihood ratios. The proposed approach suggests also an alternative performance criterion in the analysis of the procedure by replacing the expected detection delay by the corresponding K-L divergence. We show that, under the false alarm probability constraint, the nonparametric CUSUM rule is optimal in the sense that it ensures the logarithmic asymptotic for the detection delay. [ABSTRACT FROM AUTHOR]

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, code words are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources R^ (D) as well as the optimal excess-distortion exponent. This completes a previous result which showed that R^ (D) and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable $X$ is strictly positive with high probability. In our context, $X$ is the number of code words within target distortion $D$ of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that R^ (D) is achievable for all distortion values. Finally, the refinement technique is applied to Suen’s correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent. [ABSTRACT FROM AUTHOR]

Impulsive noise features in many modern communication systems—ranging from wireless to molecular—and is often modeled by the $\alpha $ -stable distribution. At present, the capacity of $\alpha $ -stable noise channels is not well understood, with the exception of Cauchy noise ( $\alpha = 1$ ) with a logarithmic constraint and Gaussian noise ( $\alpha = 2$ ) with a power constraint. In this paper, we consider additive symmetric $\alpha $ -stable noise channels with $\alpha \in (1,2]$ . We derive bounds for the capacity with an absolute moment constraint. We then compare our bounds with a numerical approximation via the Blahut–Arimoto algorithm, which provides insight into the effect of noise parameters on the bounds. In particular, we find that our lower bound is in good agreement with the numerical approximation for $\alpha $ near 2. [ABSTRACT FROM AUTHOR]

Consider communication over a channel whose probabilistic model is completely unknown vector-wise and is not assumed to be stationary. Communication over such channels is challenging because knowing the past does not indicate anything about the future. The existence of reliable feedback and common randomness is assumed. In a previous paper, it was shown that the Shannon capacity cannot be attained, in general, if the channel is not known. An alternative notion of capacity was defined, as the maximum rate of reliable communication by any block-coding system used over consecutive blocks. This rate was shown to be achievable for the modulo-additive channel with an individual, unknown noise sequence, and not achievable for some channels with memory. In this paper, this capacity is shown to be achievable for general channel models possibly including memory, as long as this memory fades with time. In other words, there exists a system with feedback and common randomness that, without knowledge of the channel, asymptotically performs as well as any block code, which may be designed knowing the channel. For channels in which memory does not fade with time, a weaker type of capacity is shown to be achievable. [ABSTRACT FROM AUTHOR]

This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The $\varepsilon $ -capacity of the channel is characterized and it is strictly larger than the capacity for any $\varepsilon >0$ , which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding, which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate are also obtained. [ABSTRACT FROM PUBLISHER]

It was previously shown by Hashimoto that Forney’s optimal erasure decoder can be significantly simplified, in the sense that a simplified decoder achieves the same random coding bounds, for the ensemble of independent and identically distributed codewords. In this paper, the analysis of simplified decoders is refined and generalized in several aspects. First, tighter random coding bounds for simplified decoders are derived, which equal the exact exponential behavior of the fixed composition ensemble average. Second, the exponential bounds are valid both in the erasure mode and in the list mode. Third, the analysis pertains to a rather general class of simplified decoders, including the case of mismatch in the threshold function of the decoder. Fourth, expurgated exponents, which are larger than the random coding exponents at low rates, are shown to be achievable using a significantly simpler decoder than Forney’s optimal decoder. It is shown numerically that, from the aspect of exact random coding exponents, a decoder in the spirit of Hashimoto’s is as good as Forney’s in the erasure mode, as well as in the list mode. [ABSTRACT FROM PUBLISHER]

Testing the independence of the entries of multidimensional Gaussian observations is a very important problem in statistics, with a number of applications in signal processing, radar, cognitive radio, seismography, and multiple other fields. Typically, the problem is formulated as a binary hypothesis test, whereby the presence of correlation is declared when the value of a certain statistic is higher than a certain predetermined threshold. Most of the statistics for correlation tests are constructed from the sample correlation matrix (also known as sample coherence matrix in signal processing), which is defined as a power-normalized version of the sample covariance matrix. In this paper, correlation tests constructed from linear spectral statistics (LSS) of the sample correlation matrix are analyzed under the asymptotic framework where both sample size and observation dimension become large but comparable in magnitude. A central limit theorem (CLT) is established on this class of statistics, which is valid for generally correlated Gaussian observations. Results show that LSS asymptotically fluctuate as Gaussian random variables under both the hypotheses, with an asymptotic mean and variance that can be established for each particular test. In particular, this general CLT can be used to establish the asymptotic behavior of two of the most important correlation test statistics, namely the generalized likelihood ratio test and the Frobenius norm test, under both null and alternative hypotheses. As a by-product, it is established that LSS of sample covariance and sample correlation matrices have exactly the same first order behavior, but quite different asymptotic fluctuations in the second-order regime. In both the cases, the LSS asymptotically behave as Gaussian random variables, although with quite different asymptotic means and variances. [ABSTRACT FROM PUBLISHER]

This paper considers lossy source coding of $n$ -dimensional memoryless sources and shows an explicit approximation to the minimum source coding rate required to sustain the probability of exceeding distortion $d$ no greater than $\epsilon $ , which is simpler than known dispersion-based approximations. Our approach takes inspiration in the celebrated classical result stating that the Shannon lower bound to rate-distortion function becomes tight in the limit $d \to 0$ . We formulate an abstract version of the Shannon lower bound that recovers both the classical Shannon lower bound and the rate-distortion function itself as special cases. Likewise, we show that a nonasymptotic version of the abstract Shannon lower bound recovers all previously known nonasymptotic converses. A necessary and sufficient condition for the Shannon lower bound to be attained exactly is presented. It is demonstrated that whenever that condition is met, the rate-dispersion function is given simply by the varentropy of the source. Remarkably, all finite alphabet sources with balanced distortion measures satisfy that condition in the range of low distortions. Most continuous sources violate that condition. Still, we show that lattice quantizers closely approach the nonasymptotic Shannon lower bound, provided that the source density is smooth enough and the distortion is low. This implies that fine multidimensional lattice coverings are nearly optimal in the rate-distortion sense even at finite $n$ . The achievability proof technique is based on a new bound on the output entropy of lattice quantizers in terms of the differential entropy of the source, the lattice cell size, and a smoothness parameter of the source density. The technique avoids both the usual random coding argument and the simplifying assumption of the presence of a dither signal. [ABSTRACT FROM PUBLISHER]

Fundamental relations between information and estimation have been established in the literature for the discrete-time Gaussian and Poisson channels. In this paper, we demonstrate that such relations hold for a much larger class of observation models. We introduce the natural family of discrete-time Lévy channels where the distribution of the output conditioned on the input is infinitely divisible. For Lévy channels, we establish new representations relating the mutual information between the channel input and output to an optimal expected estimation loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. We demonstrate the richness of our results by working out two examples of Lévy channels, namely the gamma channel and the negative binomial channel, with corresponding relations between information and estimation. Extensions to the setting of mismatched estimation are also presented. [ABSTRACT FROM AUTHOR]

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the linear programming bound, which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of linear programming bounds to networks with correlated sources is largely open. Source dependence is usually specified through a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependences via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”. Using such auxiliary random variables, we also give implicit and explicit outer bounds on the capacity of networks with correlated sources. The characterisation of correlation or joint distribution via Shannon entropy functions is also applicable to other information measures, such as Rényi entropy and Tsallis entropy. [ABSTRACT FROM AUTHOR]

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$ . In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of simulating a discrete memoryless channel (DMC) from another DMC under an average-case and an exact model. We present several achievability and infeasibility results, with tight characterizations in special cases. In particular, for the exact model, we fully characterize when a binary symmetric channel can be simulated from a binary erasure channel when there is no shared randomness. We also provide infeasibility and achievability results for the simulation of a binary channel from another binary channel in the case of no shared randomness. To do this, we use the properties of Rényi capacity of a given order. We also introduce a notion of “channel diameter” which is shown to be additive and satisfy a data processing inequality. [ABSTRACT FROM PUBLISHER]

Recently, a secrecy measure based on list-reconstruction has been proposed, in which a wiretapper is allowed to produce a list of 2^mRL reconstruction sequences and the secrecy is measured by the minimum distortion over the entire list. In this paper, we show that this list secrecy problem is equivalent to the one with secrecy measured by a new quantity lossy equivocation, which is proved to be the minimum optimistic one-achievable source coding rate (the minimum coding rate needed to reconstruct the source within target distortion with positive probability for infinitely many blocklengths) of the source with the wiretapped signal as two-sided information, and also can be seen as a lossy extension of conventional equivocation. Upon this (or list) secrecy measure, we study source-channel secrecy problem in the discrete memoryless Shannon cipher system with noisy wiretap channel. Two inner bounds and an outer bound on the achievable region of secret key rate, list rate, wiretapper distortion, and distortion of legitimate user are given. The inner bounds are derived by using uncoded scheme and (operationally) separate scheme, respectively. Thanks to the equivalence between lossy-equivocation secrecy and list secrecy, information spectrum method is leveraged to prove the outer bound. As special cases, the admissible region for the case of degraded wiretap channel or lossless communication for legitimate user has been characterized completely. For both these two cases, separate scheme is proved to be optimal. Interestingly, however, separation indeed suffers performance loss for other certain cases. Besides, we also extend our results to characterize the achievable region for Gaussian communication case. As a side product, optimistic lossy source coding has also been addressed. [ABSTRACT FROM PUBLISHER]

Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = \mathcal O(N^1- \delta ) for some \delta > 0 . The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that \Theta (D\log (N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity ( \mathcal O\left (D\log (N)\right ) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” ( \mathcal O\left (\log (D)\right ) ). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires \mathcal O\left (D\log (D)\log (N)\right ) tests and has a decoding complexity of \mathcal O(D(\log N+\log ^2D)) . Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as \mathcal O(D(\log N+\log ^2D)) . For all three settings, the probability of error of our algorithms scales as \mathcal O\left (1/(poly(D)\right ) . For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of obtaining 1-of-2 string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users’ inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice–Bob and Alice–Eve), we derive the 1-of-2 string OT capacity for both 2-privacy (when Eve can collude with either Alice or Bob) and 1-privacy (when no such collusion is allowed). We generalize these capacity results to 1-of- $N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice–Bob and Alice–Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice–Bob and Bob–Eve) and 1-of-2 string OT is desired between Alice and Bob with 1-privacy. For this setup, we derive an upper and lower bound on the 1-of-2 string OT capacity which match in one of two possible parameter regimes. [ABSTRACT FROM PUBLISHER]

Shannon’s analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume M_ \mathrm avg^*(n,\epsilon ) of length- n codes subject to an average decoding error probability \epsilon is shown to satisfy the following tight asymptotic lower and upper bounds as n \to \infty : , where C is the Shannon capacity, V_\epsilon is the \epsilon -channel dispersion, or second-order coding rate, Q and \overline A_\epsilon are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap \overline A_\epsilon - \underline A_\epsilon is one nat for weakly symmetric channels in the Cover–Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the $Z$ channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacity-achieving input distribution modified by an O(1/\sqrt {n}) correction term. [ABSTRACT FROM PUBLISHER]

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe’s work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray–Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities. [ABSTRACT FROM PUBLISHER]

An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability $p$ . An $(l, r, n)$ -regular pooling graph is a bipartite graph in which the left nodes have degree $l$ , the right nodes have degree $r$ , and $n$ is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an $(l, r, n)$ -regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system. [ABSTRACT FROM PUBLISHER]

Integer-Forcing (IF) is a new framework, based on compute-and-forward, for decoding multiple integer linear combinations from the output of a Gaussian multiple-input multiple-output channel. This paper applies the IF approach to arrive at a new low-complexity scheme, IF source coding, for distributed lossy compression of correlated Gaussian sources under a minimum mean squared error distortion measure. All encoders use the same nested lattice codebook. Each encoder quantizes its observation using the fine lattice as a quantizer and reduces the result modulo the coarse lattice, which plays the role of binning. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. In general, the linear combinations have smaller average powers than the original signals. This allows to increase the density of the coarse lattice, which in turn translates to smaller compression rates. We also propose and analyze a one-shot version of IF source coding that is simple enough to potentially lead to a new design principle for analog-to-digital converters that can exploit spatial correlations between the sampled signals. [ABSTRACT FROM AUTHOR]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (second) part provides a foundation of polarization theory based on the ergodic theory of binary operations which we developed in the first part. We show that a binary operation is polarizing if and only if it is uniformity preserving and its right-inverse is strongly ergodic. The rate of polarization of single user channels is studied. It is shown that the exponent of any polarizing operation cannot exceed \frac 12 , which is the exponent of quasi-group operations. We also study the polarization of multiple access channels (MAC). In particular, we show that a sequence of binary operations is MAC-polarizing if and only if each binary operation in the sequence is polarizing. It is shown that the exponent of any MAC-polarizing sequence cannot exceed \frac 12 , which is the exponent of sequences of quasi-group operations. [ABSTRACT FROM AUTHOR]

In this paper, we explore the three-node multi-terminal lossy source coding problem, which seems to offer a formidable mathematical complexity. We derive an inner bound to the general rate-distortion region of this problem, which is a natural extension of the seminal work by Kaspi on the interactive two-terminal source coding problem. It is shown that this (rather involved) inner bound contains several rate-distortion regions of some relevant source coding settings. In this way, besides the non-trivial extension of the interactive two terminal problem, our results can be seen as a generalization and hence unification of several previous works in the field. By specializing the inner bound to particular cases, we obtain some novel rate-distortion regions for several multi-terminal lossy source coding problems. [ABSTRACT FROM PUBLISHER]

Given n discrete random variables, its entropy vector is the 2^{n}-1 -dimensional vector obtained from the joint entropies of all non-empty subsets of the random variables. It is well known that there is a close relation between such an entropy vector and a certain group-characterizable vector obtained from a finite group and n of its subgroups; indeed, roughly speaking, knowing the region of all such group-characterizable vectors is equivalent to knowing the region of all entropy vectors. This correspondence may be useful for characterizing the space of entropic vectors and for designing network codes. If one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al. that linear network codes cannot achieve capacity in general network coding problems (since linear network codes come from abelian groups). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. General entropy vectors, however, do not necessarily have this property. It is, therefore, of interest to identify groups that violate the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors, which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2,q) with a prime power q \geq 5 , i.e., the projective group of 2\times 2 nonsingular matrices with entries in \mathbb Fq . We further interpret this family of groups, and their subgroups, using the theory of group actions and identify the subgroups as certain stabilizers. We also extend the construction to more general groups such as PGL(n,q) and $GL(n,q)$ . The families of groups identified here are therefore good candidates for constructing network codes more powerful than linear network codes, and we discuss some considerations for constructing such group network codes. [ABSTRACT FROM PUBLISHER]

Treating interference as noise (TIN) as the most appropriate approach in dealing with interference and the conditions on its optimality has attracted the interest of researchers recently. However, our knowledge on necessary and sufficient conditions of TIN is restricted to a few setups with limited number of users. In this paper, we study the optimality of TIN in terms of the generalized degrees of freedom (GDoF) for a fundamental network, namely, the $M\times 2$ X-channel. To this end, the achievable GDoF of TIN with power allocations at the transmitters is studied. It turns out that the transmit power allocation maximizing the achievable GDOF is given by on–off signaling as long as the receivers use TIN. This leads to two variants of TIN, namely, P2P-TIN and 2-IC-TIN. While in the first variant the $M\times 2$ X-channel is reduced to a point-to-point (P2P) channel, in the second variant, the setup is reduced to a two-user interference channel in which the receivers use TIN. The optimality of these two variants is studied separately. To this end, novel genie-aided upper bounds on the capacity of the X-channel are established. The conditions on the optimality of P2P-TIN can be summarized as follows. P2P-TIN is GDoF-optimal if there exists a dominant multiple access channel or a dominant broadcast channel embedded in the X channel. Furthermore, the necessary and sufficient conditions on the GDoF-optimality of 2-IC-TIN are presented. Interestingly, it turns out that operating the $M\times 2$ X-channel in the 2-IC-TIN mode might be still GDOF optimal, although the conditions given by Geng et al. are violated. However, 2-IC-TIN is sub-optimal if there exists a single interferer which causes sufficiently strong interference at both receivers. The comparison of the results with the state of the art shows that the GDOF optimality of TIN is expanded significantldy. [ABSTRACT FROM PUBLISHER]

The impact of cooperation on interference management is investigated by studying an elemental wireless network, the so-called symmetric interference relay channel (IRC), from a generalized degrees of freedom (GDoF) perspective. This is motivated by the fact that the deployment of relays is considered as a remedy to overcome the bottleneck of current systems in terms of achievable rates. The focus of this paper is on the regime in which the interference link is weaker than the source-relay link in the IRC. Our approach toward studying the GDoF goes through the capacity analysis of the linear deterministic IRC (LD-IRC). New upper bounds on the sum capacity of the LD-IRC based on genie-aided approaches are established. These upper bounds together with some existing upper bounds are achieved by using four novel transmission schemes. Extending the upper bounds and the transmission schemes to the Gaussian case, the GDoF of the Gaussian IRC is characterized for the aforementioned regime. This completes the GDoF results available in the literature for the symmetric GDoF. It turns out that even if the incoming and outgoing links of the relay are both weaker than the desired channel, involving a relay can increase the GDoF. Interestingly, utilizing the relay in this case can increase the slope of the GDoF from −2 [in the interference channel (IC)] to −1 or 0. This shrinks the regime where ignoring the interference by treating it as noise is optimal. Furthermore, the analysis shows that if the relay ingoing and outgoing links are sufficiently strong, the relay is able to neutralize the interference completely. In this case, the bottleneck of the transmission will be the interference links, and hence, the GDoF increases if the interference link gets stronger. It is shown that in the strong interference regime, in contrast to the IC, the GDoF can be a monotonically decreasing function of the interference level. [ABSTRACT FROM PUBLISHER]

This paper gives improved Rényi entropy power inequalities (R-EPIs). Consider a sum Sn = \sum k=1^{n} Xk of n independent continuous random vectors taking values on {\mathbb {R}}^{d} , and let \alpha \in [1, \infty ] . An R-EPI provides a lower bound on the order- \alpha Rényi entropy power of S_{n} that, up to a multiplicative constant (which may depend in general on n, \alpha , d$ ), is equal to the sum of the order- \alpha $ Rényi entropy powers of the n$ random vectors . For $\alpha =1$ , the R-EPI coincides with the well-known entropy power inequality by Shannon. The first improved R-EPI is obtained by tightening the recent R-EPI by Bobkov and Chistyakov, which relies on the sharpened Young’s inequality. A further improvement of the R-EPI also relies on convex optimization and results on rank-one modification of a real-valued diagonal matrix. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of quickly detecting an unknown change in the conditional densities of a dependent stochastic process. In contrast to the existing quickest change detection approaches for dependent stochastic processes, we propose minimax robust versions of the popular Lorden, Pollak, and Bayesian criteria for when there is uncertainty about the parameter of the post-change conditional densities. Under an information-theoretic Pythagorean inequality condition on the uncertainty set of possible post-change parameters, we identify asymptotic minimax robust solutions to our Lorden, Pollak, and Bayesian problems. Finally, through simulation examples, we illustrate that asymptotically minimax robust rules can provide detection performance comparable to the popular (but more computationally expensive) generalized likelihood ratio rule. [ABSTRACT FROM PUBLISHER]

We consider a communication network consisting of nodes and directed edges that connect the nodes. The network may contain cycles. The communications are slotted where the duration of each time slot is equal to the maximum propagation delay experienced by the edges. The edges with negligible delays are allowed to be operated before the other edges in each time slot. For any pair of adjacent edges $(\ell , i)$ and $(i,j)$ , where $(\ell ,i)$ terminates at node $i$ and $(i,j)$ originates from node $i$ , we say $(\ell ,i)$ incurs zero delay on $(i,j)$ if $(\ell ,i)$ is operated before $(i,j)$ ; otherwise, we say $(\ell ,i)$ incurs a unit delay on $(i,j)$ . In the classical model, every edge incurs a unit delay on every adjacent edge and the cut-set bound is a well-known outer bound on the capacity region. In this paper, we investigate the multimessage multicast network (MMN) consisting of independent channels, where each channel is associated with a set of edges and each edge may incur zero delay on some other edges. Our result reveals that the capacity region of the MMN with independent channels and zero-delay edges lies within the classical cut-set bound despite a violation of the unit-delay assumption. [ABSTRACT FROM PUBLISHER]

Let N be a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring N is believed to be hard. The RSA assumption states that, given an a chosen uniformly at random from and an e \in {\mathbb {N}} \setminus \{1\} such that \gcd (e, \phi (N)) = 1 , it is computationally hard to find an x\in \mathbb Z N such that x^{e} - a \equiv 0 \pmod N . When complexity-theoretic (relative) lower bounds for certain cryptographic problems in a general model of computation seem to elude discovery, a common practice in cryptography is to give proofs of computational security in meaningful restricted models of computation. An example of such a restricted model that is interesting in cryptography is the generic group model that has been used for proving lower bounds for the discrete logarithm problem and other related problems. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. In this paper, we prove that the problem of factoring $N$ can be efficiently reduced to solving the RSA problem on {\mathbb {Z}}_{N} in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality. This provides evidence toward the soundness of the RSA encryption and digital signature scheme, in particular showing that under the factoring assumption, they are not vulnerable to certain kinds of cryptanalytic attacks. [ABSTRACT FROM AUTHOR]

Let \mathcal N=\1,\ldots ,n\ . The entropy function h of a set of n discrete random variables \{X_{i}:i\in \mathcal {N} \} is a 2^{n} -dimensional vector whose entries are \text h( \mathcal A)\triangleq H(X \mathcal A) , \mathcal A\subset \mathcal {N} , the (joint) entropies of the subsets of the set of n random variables with H(X_\emptyset )=0 by convention. The set of all entropy functions for n discrete random variables, denoted by , is called the entropy region for n . Characterization of \Gamma ^*n and its closure \overline {\Gamma ^*n} are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider partition-symmetrical entropy functions. Let p=\ \mathcal N1,\ldots , \mathcal {Nt\} be a t -partition of \mathcal {N} . An entropy function \bf h is called p -symmetrical if for all {\mathcal{ A}},{\mathcal{ B}} \subset {\mathcal{ N}} , \text {h}({\mathcal{ A}}) = \text {h}({\mathcal{ B}}) whenever \mathcal A \cap \mathcal Ni = {\mathcal{ B}} \cap \mathcal Ni , i = 1, \ldots ,t . The set of all the p -symmetrical entropy functions, denoted by \Psi ^{*}_{p} , is called p -symmetrical entropy function region. We prove that \overline \Psi ^*p , the closure of \Psi ^{*}p , is completely characterized by Shannon-type information inequalities if and only if $p$ is the 1-partition or a 2-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems. [ABSTRACT FROM AUTHOR]

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relationship by Guo et al., together with its numerous extensions, has great theoretical significance and various practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the absence of its extensions to such channels. In this paper, we propose the extensions of the I-MMSE relationship to discrete-time and continuous-time Gaussian channels with feedback and/or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn’s identity. [ABSTRACT FROM AUTHOR]

This paper starts with new aliasing-truncation error upper bounds in the sampling theorem for non-bandlimited stochastic signals. Then, it investigates Lp([0,T]) approximations of the sub-Gaussian random signals. Explicit truncation error upper bounds are established. The obtained rate of convergence provides a constructive algorithm for determining the sampling rate and the sample size in the truncated Whittaker-Kotel’nikov-Shannon expansions to ensure the approximation of the sub-Gaussian signals with given accuracy and reliability. Some numerical examples are presented. [ABSTRACT FROM AUTHOR]

The best known inner bound for the two-user discrete memoryless interference channel is the Han–Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing). [ABSTRACT FROM PUBLISHER]

This paper extends the empirical minimum divergence approach for models, which satisfy linear constraints with respect to the probability measure of the underlying variable (moment constraints) to the case where such constraints pertain to its quantile measure (called here semiparametric quantile models). The case when these constraints describe shape conditions as handled by the L-moments is considered, and both the description of these models as well as the resulting nonclassical minimum divergence procedures are presented. These models describe neighbourhoods of classical models used mainly for their tail behavior, for example, neighborhoods of Pareto or Weibull distributions, with which they may share the same first L-moments. The properties of the resulting estimators are illustrated by simulated examples comparing maximum likelihood estimators on Pareto and Weibull models to the minimum chi-square empirical divergence approach on semiparametric quantile models, and others. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate an instance of the Heegard–Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both the decoders, and the other is reproduced within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. In particular, we show that the optimal coding scheme for this setting is one in which the common description to be recovered by both the decoders should allow to involve all or part of the source that is to be reproduced at only one decoder. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both the decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder–decoder reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function. [ABSTRACT FROM PUBLISHER]

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the corresponding sets of achievable rate tuples. Our strong converse result implies that for any DM-MMN of these classes, the average error probabilities of any sequence of codes operated at a rate tuple belonging to the exterior of the cut-set bound must tend to one (and are not simply bounded away from zero) as the block length grows. Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence. [ABSTRACT FROM PUBLISHER]

In this paper, a free deterministic equivalent is proposed for the capacity analysis of the multi-input multi-output (MIMO) multiple access channel (MAC) with a more general channel model compared to previous works. In particular, a MIMO MAC with one base station (BS) equipped with several distributed antenna sets is considered. Each link between a user and a BS antenna set forms a jointly correlated Rician fading channel. The analysis is based on operator-valued free probability theory, which broadens the range of applicability of free probability techniques tremendously. By replacing independent Gaussian random matrices with operator-valued random variables satisfying certain operator-valued freeness relations, the free deterministic equivalent of the considered channel Gram matrix is obtained. The Shannon transform of the free deterministic equivalent is derived, which provides an approximate expression for the ergodic input-output mutual information of the channel. The sum-rate capacity achieving input covariance matrices are also derived based on the approximate ergodic input-output mutual information. The free deterministic equivalent results are easy to compute, and simulation results show that these approximations are numerically accurate and computationally efficient. [ABSTRACT FROM PUBLISHER]

We revisit the problem of secret key agreement using interactive public communication for two parties and propose a new secret key agreement protocol. The protocol attains the secret key capacity for general observations and attains the second-order asymptotic term in the maximum length of a secret key for independent and identically distributed observations. In contrast to the previously suggested secret key agreement protocols, the proposed protocol uses interactive communication. In fact, the standard one-way communication protocol used prior to this paper fails to attain the asymptotic results above. Our converse proofs rely on a recently established upper bound for secret key lengths. Both our lower and upper bounds are derived in a single-shot setup and the asymptotic results are obtained as corollaries. [ABSTRACT FROM PUBLISHER]

In recent years, solutions to various hypothesis testing problems in the asymptotic setting have been proposed using the results from large deviation theory. Such tests are optimal in terms of appropriately defined error exponents. For the practitioner, however, error probabilities in the finite sample size setting are more important. In this paper, we show how results on weak convergence of the test statistic can be used to obtain better approximations for the error probabilities in the finite sample size setting. While this technique is popular among statisticians for common tests, we demonstrate its applicability for several recently proposed asymptotically optimal tests, including tests for robust goodness of fit, homogeneity tests, outlier hypothesis testing, and graphical model estimation. [ABSTRACT FROM PUBLISHER]