Anantharam, Jog, and Nair recently unified the Shannon–Stam inequality and the entropic form of the Brascamp–Lieb inequalities under a common inequality. They left open the problems of extremizability and characterization of extremizers. Both questions are resolved in the present paper. Separately, we show that the Anantharam–Jog–Nair inequality may be derived as a corollary of the Brascamp–Lieb inequalities, establishing a formal equivalence between the two.

Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. However, LDP applies uniform protection to all data features, including less sensitive ones, which degrades performance of downstream tasks. To overcome this limitation, we propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific privacy quantification. This more nuanced approach complements LDP by adjusting privacy protection according to the sensitivity of each feature, enabling improved performance of downstream tasks without compromising privacy. We characterize the properties of BCDP and articulate its connections with standard non-Bayesian privacy frameworks. We further apply our BCDP framework to the problems of private mean estimation and ordinary least-squares regression. The BCDP-based approach obtains improved accuracy compared to a purely LDP-based approach, without compromising on privacy.

We consider an assortment selection and pricing problem in which a seller has $N$ different items available for sale. In each round, the seller observes a $d$-dimensional contextual preference information vector for the user, and offers to the user an assortment of $K$ items at prices chosen by the seller. The user selects at most one of the products from the offered assortment according to a multinomial logit choice model whose parameters are unknown. The seller observes which, if any, item is chosen at the end of each round, with the goal of maximizing cumulative revenue over a selling horizon of length $T$. For this problem, we propose an algorithm that learns from user feedback and achieves a revenue regret of order $\widetilde{\mathcal{O}}(d \sqrt{K T} / L_0 )$ where $L_0$ is the minimum price sensitivity parameter. We also obtain a lower bound of order $\Omega(d \sqrt{T}/ L_0)$ for the regret achievable by any algorithm.

Previous works in the differential privacy literature that allow users to choose their privacy levels typically operate under the heterogeneous differential privacy (HDP) framework with the simplifying assumption that user data and privacy levels are not correlated. Firstly, we demonstrate that the standard HDP framework falls short when user data and privacy demands are allowed to be correlated. Secondly, to address this shortcoming, we propose an alternate framework, Add-remove Heterogeneous Differential Privacy (AHDP), that jointly accounts for user data and privacy preference. We show that AHDP is robust to possible correlations between data and privacy. Thirdly, we formalize the guarantees of the proposed AHDP framework through an operational hypothesis testing perspective. The hypothesis testing setup may be of independent interest in analyzing other privacy frameworks as well. Fourthly, we show that there exists non-trivial AHDP mechanisms that notably do not require prior knowledge of the data-privacy correlations. We propose some such mechanisms and apply them to core statistical tasks such as mean estimation, frequency estimation, and linear regression. The proposed mechanisms are simple to implement with minimal assumptions and modeling requirements, making them attractive for real-world use. Finally, we empirically evaluate proposed AHDP mechanisms, highlighting their trade-offs using LLM-generated synthetic datasets, which we release for future research.

We study the problem of robust estimation under heterogeneous corruption rates, where each sample may be independently corrupted with a known but non-identical probability. This setting arises naturally in distributed and federated learning, crowdsourcing, and sensor networks, yet existing robust estimators typically assume uniform or worst-case corruption, ignoring structural heterogeneity. For mean estimation for multivariate bounded distributions and univariate gaussian distributions, we give tight minimax rates for all heterogeneous corruption patterns. For multivariate gaussian mean estimation and linear regression, we establish the minimax rate for squared error up to a factor of $\sqrt{d}$, where $d$ is the dimension. Roughly, our findings suggest that samples beyond a certain corruption threshold may be discarded by the optimal estimators -- this threshold is determined by the empirical distribution of the corruption rates given.

Differential Privacy (DP) is a well-established framework to quantify privacy loss incurred by any algorithm. Traditional formulations impose a uniform privacy requirement for all users, which is often inconsistent with real-world scenarios in which users dictate their privacy preferences individually. This work considers the problem of mean estimation, where each user can impose their own distinct privacy level. The algorithm we propose for this problem is shown to be minimax optimal and has a near-linear run-time. Our results elicit an interesting saturation phenomenon that occurs. Namely, the privacy requirements of the most stringent users dictate the overall error rates. As a consequence, users with less but differing privacy requirements are all given more privacy than they require, in equal amounts. In other words, these privacy-indifferent users are given a nontrivial degree of privacy for free, without any sacrifice in the performance of the estimator.

Differential Privacy (DP) is a well-established framework to quantify privacy loss incurred by any algorithm. Traditional DP formulations impose a uniform privacy requirement for all users, which is often inconsistent with real-world scenarios in which users dictate their privacy preferences individually. This work considers the problem of mean estimation under heterogeneous DP constraints, where each user can impose their own distinct privacy level. The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels. Our results elicit an interesting saturation phenomenon that occurs as one group’s privacy level is relaxed, while the other group’s privacy level remains constant. Namely, after a certain point, further relaxing the privacy requirement of the former group does not improve the performance of the minimax optimal mean estimator. Thus, the central server can offer a certain degree of privacy without any sacrifice in performance.

Online pricing has been the focus of extensive research in recent years, particularly in the context of selling an item to sequentially arriving users. However, what if a provider wants to maximize revenue by selling multiple items to multiple users in each round? This presents a complex problem, as the provider must intelligently offer the items to those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with $N$ users, $M$ items, and load $L$ (which roughly corresponds to the maximum number of simultaneous allocations possible), our algorithms achieve regret of order $O(NM\log\log(LT))$ under fixed valuations model, $\widetilde{O}(\sqrt{NMLT})$ under random experiences model and $\widetilde{O}(\sqrt{NMLT})$ under random valuations model in $T$ rounds.

We establish a family of sharp entropy inequalities with Gaussian extremizers. These inequalities hold for certain dependent random variables, namely entropy-maximizing couplings subject to information constraints. Several well-known results, such as the Zamir-Feder and Brunn-Minkowski inequalities, follow as special cases.

Motivated by recent developments in serverless systems for large-scale computation as well as improvements in scalable randomized matrix algorithms, we develop OverSketched Newton, a randomized Hessian-based optimization algorithm to solve large-scale convex optimization problems in serverless systems. OverSketched Newton leverages matrix sketching ideas from Randomized Numerical Linear Algebra to compute the Hessian approximately. These sketching methods lead to inbuilt resiliency against stragglers that are a characteristic of serverless architectures. Depending on whether or not the problem is strongly convex, we propose different iteration updates using the approximate Hessian. For both cases, we establish convergence guarantees for OverSketched Newton, and we empirically validate our results by solving large-scale supervised learning problems on real-world datasets. Experiments demonstrate a reduction of ~50% in total running time on AWS Lambda, compared to state-of-the-art distributed optimization schemes.

Inexpensive cloud services, such as serverless computing, are often vulnerable to straggling nodes that increase the end-to-end latency for distributed computation. We propose and implement simple yet principled approaches for straggler mitigation in serverless systems for matrix multiplication and evaluate them on several common applications from machine learning and high-performance computing. The proposed schemes are inspired by error-correcting codes and employ parallel encoding and decoding over the data stored in the cloud using serverless workers. This creates a fully distributed computing framework without using a master node to conduct encoding or decoding, which removes the computation, communication and storage bottleneck at the master. On the theory side, we establish that our proposed scheme is asymptotically optimal in terms of decoding time and provide a lower bound on the number of stragglers it can tolerate with high probability. Through extensive experiments, we show that our scheme outperforms existing schemes such as speculative execution and other coding theoretic methods by at least 25%.

We establish a nonasymptotic lower bound on the L2minimax risk for a class of generalized linear models. It is further shown that the minimax risk for the canonical linear model matches this lower bound up to a universal constant. Therefore, the canonical linear model may be regarded as most favorable among the considered class of generalized linear models (in terms of minimax risk). The proof makes use of an information-theoretic Bayesian Cramér-Rao bound for log-concave priors, established by Aras et al. (2019).

We establish a new class of minimax prediction error bounds for generalized linear models. Our bounds significantly improve previous results when the design matrix is poorly structured, including natural cases where the matrix is wide or does not have full column rank. Apart from the typical $L_2$ risks, we study a class of entropic risks which recovers the usual $L_2$ prediction and estimation risks, and demonstrate that a tight analysis of Fisher information can uncover underlying structural dependency in terms of the spectrum of the design matrix. The minimax approach we take differs from the traditional metric entropy approach, and can be applied to many other settings.

The Brascamp-Lieb inequality in functional analysis can be viewed as a measure of the “uncorrelatedness” of a joint probability distribution. We define the smooth Brascamp-Lieb (BL) divergence as the infimum of the best constant in the Brascamp-Lieb inequality under a perturbation of the joint probability distribution. An information spectrum upper bound on the smooth BL divergence is proved, using properties of the subgradient of a certain convex functional. In particular, in the i.i.d. setting, such an infimum converges to the best constant in a certain mutual information inequality. We then derive new single-shot converse bounds for the omniscient helper common randomness generation problem and the Gray-Wyner source coding problem in terms of the smooth BL divergence, where the proof relies on the functional formulation of the Brascamp-Lieb inequality. Exact second-order rates are thus obtained in the stationary memoryless and nonvanishing error setting. These offer rare instances of strong converses/second-order converses for continuous sources when the rate region involves auxiliary random variables.

Under minimal regularity assumptions, we establish a family of information-theoretic Bayesian Cramér-Rao bounds, indexed by probability measures that satisfy a logarithmic Sobolev inequality. This family includes as a special case the known Bayesian Cramér-Rao bound (or van Trees inequality), and its less widely known entropic improvement due to Efroimovich. For the setting of a log-concave prior, we obtain a Bayesian Cramér-Rao bound which holds for any (possibly biased) estimator and, unlike the van Trees inequality, does not depend on the Fisher information of the prior.

We propose OverSketch, an approximate algorithm for distributed matrix multiplication in serverless computing. OverSketch leverages ideas from matrix sketching and high-performance computing to enable cost-efficient multiplication that is resilient to faults and straggling nodes pervasive in low-cost serverless architectures. We establish statistical guarantees on the accuracy of OverSketch and empirically validate our results by solving a large-scale linear program using interior-point methods and demonstrate a 34% reduction in compute time on AWS Lambda.

A quantitative entropic central limit theorem is established for the sum of i.i.d. radially symmetric random vectors having dimension greater than one. In contrast to recent related work, strong regularity assumptions - such as positive spectral gap or log-concavity of densities - are not needed. However, this added flexibility comes at the expense of an assumption of radial symmetry.

When one of the random summands is Gaussian, we sharpen the entropy power inequality (EPI) in terms of the strong data processing function for Gaussian channels. Among other consequences, this `strong' EPI generalizes the vector extension of Costa's EPI to non-Gaussian channels in a precise sense. This leads to a new reverse EPI and, as a corollary, sharpens Stam's uncertainty principle relating entropy power and Fisher information (or, equivalently, Gross' logarithmic Sobolev inequality). Applications to network information theory are also given, including a short self-contained proof of the rate region for the two-encoder quadratic Gaussian source coding problem and a new outer bound for the one-sided Gaussian interference channel.

We establish quantitative stability results for the entropy power inequality (EPI). Specifically, we show that if uniformly log-concave densities nearly saturate the EPI, then they must be close to Gaussian densities in the quadratic Kantorovich-Wasserstein distance. Furthermore, if one of the densities is Gaussian and the other is log-concave, or more generally has positive spectral gap, then the deficit in the EPI can be controlled in terms of the L1-Kantorovich-Wasserstein distance or relative entropy, respectively. As a counterpoint, an example shows that the EPI can be unstable with respect to the quadratic Kantorovich-Wasserstein distance when densities are uniformly log-concave on sets of measure arbitrarily close to one. Our stability results can be extended to non-log-concave densities, provided certain regularity conditions are met. The proofs are based on mass transportation.

We give a counterexample to the vector generalization of Costa's entropy power inequality due to Liu et al. In particular, the claimed inequality can fail if the matrix-valued parameter in the convex combination does not commute with the covariance of the additive Gaussian noise. Conversely, the inequality holds if these two matrices commute.

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of r-sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most d codeword bits. We consider both adaptive and nonadaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Such a characterization for the fixed-blocklength analog of our problem, known as the bit probe complexity of static membership, remains unknown despite considerable attention from researchers over the last few decades. We also show that locally decodable schemes for sparse sequences are able to decode 0s (frequent source symbols) of the source with far fewer probes on average than they can decode 1s (infrequent source symbols), thus rigorizing the notion that infrequent symbols require high probe complexity, even on average. Connections to the fixed-blocklength model and to communication complexity are also briefly discussed.

Consider a noisy linear observation model with an unknown permutation, based on observing y = Π* Ax* + w, where x* ∈ ℝdis an unknown vector, Π* is an unknown n x n permutation matrix, and w ∈ ℝnis additive Gaussian noise. We analyze the problem of permutation recovery in a random design setting in which the entries of matrix A are drawn independently from a standard Gaussian distribution and establish sharp conditions on the signal-to-noise ratio, sample size n, and dimension d under which Π* is exactly and approximately recoverable. On the computational front, we show that the maximum likelihood estimate of Π* is NP-hard to compute for general d, while also providing a polynomial time algorithm when d = 1.

We show that Costa's entropy power inequality, when appropriately formulated, can be precisely generalized to non-Gaussian additive perturbations. This reveals fundamental links between the Gaussian logarithmic Sobolev inequality and the convolution inequalities for entropy and Fisher information. Various consequences including a reverse entropy power inequality and information-theoretic central limit theorems are also established.

We establish quantitative stability results for the entropy power inequality (EPI) in arbitrary dimension. Specifically, we show that if uniformly log-concave densities nearly saturate the EPI, then they must be close to Gaussian densities in the quadratic Wasserstein distance. Further, if one of the densities is log-concave and the other is Gaussian, then the deficit in the EPI can be controlled in terms of the L1-Wasserstein distance. As a counterpoint, an example shows that the EPI can be unstable with respect to the quadratic Wasserstein distance even if densities are uniformly log-concave on sets of measure arbitrarily close to one. The proofs are based on optimal transportation.

We consider the multivariate linear regression model with shuffled data and additive noise, which arises in various correspondence estimation and matching problems. We focus on the denoising problem and characterize the minimax error rate up to logarithmic factors. We also analyze the performance of two versions of a computationally efficient estimator that are consistent for a large range of input parameters. Finally, we provide an exact algorithm for the noiseless problem and demonstrate its performance on an image point-cloud matching task. Our analysis also extends to datasets with missing data.

Motivation: Genetic variation in human populations is influenced by geographic ancestry due to spatial locality in historical mating and migration patterns. Spatial population structure in genetic datasets has been traditionally analyzed using either model-free algorithms, such as principal components analysis (PCA) and multidimensional scaling, or using explicit spatial probabilistic models of allele frequency evolution. We develop a general probabilistic model and an associated inference algorithm that unify the model-based and data-driven approaches to visualizing and inferring population structure. Our spatial inference algorithm can also be effectively applied to the problem of population stratification in genome-wide association studies (GWAS), where hidden population structure can create fictitious associations when population ancestry is correlated with both the genotype and the trait. Results: Our algorithm Geographic Ancestry Positioning (GAP) relates local genetic distances between samples to their spatial distances, and can be used for visually discerning population structure as well as accurately inferring the spatial origin of individuals on a two-dimensional continuum. On both simulated and several real datasets from diverse human populations, GAP exhibits substantially lower error in reconstructing spatial ancestry coordinates compared to PCA. We also develop an association test that uses the ancestry coordinates inferred by GAP to accurately account for ancestry-induced correlations in GWAS. Based on simulations and analysis of a dataset of 10 metabolic traits measured in a Northern Finland cohort, which is known to exhibit significant population structure, we find that our method has superior power to current approaches. Availability and Implementation: Our software is available at https://github.com/anand-bhaskar/gap . Contacts: [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

This special issue contains papers on models and methods in the science of information, along with their applications in diverse domains.

We tighten the entropy power inequality (EPI) when one of the random summands is Gaussian. Our strengthening is closely related to strong data processing for Gaussian channels and generalizes the (vector extension of) Costa's EPI. This leads to a new reverse EPI and, as a corollary, sharpens Stam's inequality relating entropy power and Fisher information. Applications to network information theory are given, including a short self-contained proof of the converse for the two-encoder quadratic Gaussian source coding problem. The proof of our main result is based on weak convergence and a doubling argument for establishing Gaussian optimality via rotational-invariance.

Recently developed high-throughput sequencing platforms can generate very long reads, making the perfect assembly of whole genomes information-theoretically possible [1]. One of the challenges in achieving this goal in practice, however, is that traditional assembly algorithms based on the de Bruijn graph framework cannot handle the high error rates of long-read technologies. On the other hand, overlap-based approaches such as string graphs [2] are very robust to errors, but cannot achieve the theoretical lower bounds. In particular, these methods handle the variable-length reads provided by long-read technologies in a suboptimal manner. In this work, we introduce a new assembly algorithm with two desirable features in the context of long-read sequencing: (1) it is an overlap-based method, thus being more resilient to read errors than de Bruijn graph approaches; and (2) it achieves the information-theoretic bounds even in the variable-length read setting.

We study the infimum of the best constant in a functional inequality, the Brascamp-Lieb-like inequality, over auxiliary measures within a neighborhood of a product distribution. In the finite alphabet and the Gaussian cases, such an infimum converges to the best constant in a mutual information inequality. Implications for strong converse properties of two common randomness (CR) generation problems are discussed. In particular, we prove the strong converse property of the rate region for the omniscient helper CR generation problem in the discrete and the Gaussian cases. The latter case is a rare instance of a strong converse for a continuous source when the rate region involves auxiliary random variables.

We generalize a result by Carlen and Cordero-Erausquin on the equivalence between the Brascamp-Lieb inequality and the subadditivity of relative entropy by allowing for random transformations (a broadcast channel). This leads to a unified perspective on several functional inequalities that have been gaining popularity in the context of proving impossibility results. We demonstrate that the information theoretic dual of the Brascamp-Lieb inequality is a convenient setting for proving properties such as data processing, tensorization, convexity and Gaussian optimality. Consequences of the latter include an extension of the Brascamp-Lieb inequality allowing for Gaussian random transformations, the determination of the multivariate Wyner common information for Gaussian sources, and a multivariate version of Nelson's hypercontractivity theorem. Finally we present an information theoretic characterization of a reverse Brascamp-Lieb inequality involving a random transformation (a multiple access channel).

Earlier formulations of the DNA assembly problem were all in the context of perfect assembly; i.e., given a set of reads from a long genome sequence, is it possible to perfectly reconstruct the original sequence? In practice, however, it is very often the case that the read data is not sufficiently rich to permit unambiguous reconstruction of the original sequence. While a natural generalization of the perfect assembly formulation to these cases would be to consider a rate-distortion framework, partial assemblies are usually represented in terms of an assembly graph, making the definition of a distortion measure challenging. In this work, we introduce a distortion function for assembly graphs that can be understood as the logarithm of the number of Eulerian cycles in the assembly graph, each of which correspond to a candidate assembly that could have generated the observed reads. We also introduce an algorithm for the construction of an assembly graph and analyze its performance on real genomes.

MOTIVATION: In the context of third-generation long-read sequencing technologies, read-overlap-based approaches are expected to play a central role in the assembly step. A fundamental challenge in assembling from a read-overlap graph is that the true sequence corresponds to a Hamiltonian path on the graph, and, under most formulations, the assembly problem becomes NP-hard, restricting practical approaches to heuristics. In this work, we avoid this seemingly fundamental barrier by first setting the computational complexity issue aside, and seeking an algorithm that targets information limits In particular, we consider a basic feasibility question: when does the set of reads contain enough information to allow unambiguous reconstruction of the true sequence? RESULTS: Based on insights from this information feasibility question, we present an algorithm-the Not-So-Greedy algorithm-to construct a sparse read-overlap graph. Unlike most other assembly algorithms, Not-So-Greedy comes with a performance guarantee: whenever information feasibility conditions are satisfied, the algorithm reduces the assembly problem to an Eulerian path problem on the resulting graph, and can thus be solved in linear time. In practice, this theoretical guarantee translates into assemblies of higher quality. Evaluations on both simulated reads from real genomes and a PacBio Escherichia coli K12 dataset demonstrate that Not-So-Greedy compares favorably with standard string graph approaches in terms of accuracy of the resulting read-overlap graph and contig N50. AVAILABILITY: Available at github.com/samhykim/nsg CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Large arrays of radios have been exploited for beamforming and null steering in both radar and communication applications, but cost and form factor limitations have precluded their use in commercial systems. This paper discusses how to build arrays that enable multiuser massive multiple-input-multiple-output (MIMO) and aggressive spatial multiplexing with many users sharing the same spectrum. The focus of the paper is the energy- and cost-efficient realization of these arrays in order to enable new applications. Distributed algorithms for beamforming are proposed, and the optimum array size is considered as a function of the performance of the receiver, transmitter, frequency synthesizer, and signal distribution within the array. The effects of errors such as phase noise and synchronization skew across the array are analyzed. The paper discusses both RF frequencies below 10 GHz, where fully digital techniques are preferred, and operation at millimeter (mm)-wave bands where a combination of digital and analog techniques are needed to keep cost and power low.

We consider a coded cooperative data exchange problem with the goal of generating a secret key. In particular, we investigate the number of public transmissions required for a set of clients to agree on a secret key with probability one, subject to the constraint that it remains private from an eavesdropper. Although the problems are closely related, we prove that secret key generation with the fewest number of linear transmissions is NP-hard, while it is known that the analogous problem in the traditional cooperative data exchange setting can be solved in polynomial time. In doing this, we completely characterize the best possible performance of linear coding schemes, and also prove that linear codes can be strictly suboptimal. Finally, we extend the single-key results to characterize the minimum number of public transmissions required to generate a desired integer number of statistically independent secret keys.

Beginning with work by Avestimehr, Diggavi and Tse, there have been a series of papers showing that the capacity of Gaussian relay networks can be closely approximated by the cutset bound. More precisely, it is known that the gap between the cutset bound and capacity in these networks can be bounded by a function that grows linearly with the number of nodes in the network and is otherwise independent of network topology and channel configurations. We argue that this linear gap is fundamental to such approximations, and prove that improvement to a sublinear function is possible if, and only if, capacity is equal to the cutset bound for all Gaussian relay networks.

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of r-sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most d codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Notably, such a characterization for the fixed-blocklength analog of our problem remains unknown, despite considerable research efforts. Connections to communication complexity are also briefly discussed.

While most current high-throughput DNA sequencing technologies generate short reads with low error rates, emerging sequencing technologies generate long reads with high error rates. A basic question of interest is the tradeoff between read length and error rate in terms of the information needed for the perfect assembly of the genome. Using an adversarial erasure error model, we make progress on this problem by establishing a critical read length, as a function of the genome and the error rate, above which perfect assembly is guaranteed. For several real genomes, including those from the GAGE dataset, we verify that this critical read length is not significantly greater than the read length required for perfect assembly from reads without errors.

In their recent paper “Canalizing Boolean Functions Maximize Mutual Information,” Klotzet al.argued that canalizing Boolean functions maximize certain mutual informations by an argument involving Fourier analysis on the hypercube. This note supplies short new proofs of their results based on a coupling argument and also clarifies a point on the necessity of considering randomized functions.

The problem of performing similarity queries on compressed data is considered. We focus on the quadratic similarity measure, and study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on the compressed data. For a Gaussian source, we show that the queries can be answered reliably if and only if the compression rate exceeds a given threshold-the identification rate-which we explicitly characterize. Moreover, when compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that, as with classical compression, the Gaussian source requires the largest compression rate among sources with a given variance. Moreover, a robust scheme is described that attains this maximal rate for any source distribution.

We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captures the benefit of side information for performing inference on a random variable under this loss function. When such a measure satisfies a natural data processing property, and the random variable of interest has alphabet size greater than two, we show that it is uniquely characterized by the mutual information, and the corresponding loss function coincides with logarithmic loss. In doing so, our work provides a new characterization of mutual information, and justifies its use as a measure of relevance. When the alphabet is binary, we characterize the only admissible forms the measure of relevance can assume while obeying the specified data processing property. Our results naturally extend to measuring the causal influence between stochastic processes, where we unify different causality measures in the literature as instantiations of directed information.

Advances in lattice-based cryptography are enabling the use of public key algorithms (PKAs) in power-constrained ad hoc and sensor network devices. Unfortunately, while many wireless networks are dominated by group communications, PKAs are inherently unicast—i.e., public/private key pairs are generated by data destinations. To fully realize public key cryptography in these networks, lightweight PKAs should be augmented with energy-efficient mechanisms for group key agreement. We consider a setting where master keys are loaded on clients according to an arbitrary distribution. We present a protocol that uses session keys derived from those master keys to establish a group key that is information-theoretically secure. When master keys are distributed randomly, our protocol requires$O(\log_b t)$multicasts, where$1-1/b$is the probability that a given client possesses a given master key. The minimum number of public multicast transmissions required for a set of clients to agree on a secret key in our setting was recently characterized. The proposed protocol achieves the best possible approximation to that optimum that is computable in polynomial time. Moreover, the computational requirements of our protocol compare favorably to multi-party extensions of Diffie-Hellman key exchange.

We consider a cooperative data exchange problem with the goal of generating a secret key. Specifically, we investigate the number of public transmissions required for a set of clients to agree on a secret key with probability one, subject to the constraint that it remains private from an eavesdropper. Although the problems are closely related, we prove that secret key generation with fewest linear transmissions is NP-hard, while it is known that the analogous problem in traditional cooperative data exchange can be solved in polynomial time. In doing this, we completely characterize the best-possible performance of linear coding schemes, and also prove that linear codes can be strictly suboptimal.

This paper analyzes the distribution of the codeword lengths of the optimal lossless compression code without prefix constraints both in the non-asymptotic regime and in the asymptotic regime. The technique we use is based on upper and lower bounding the cumulant generating function of the optimum codeword lengths. In the context of prefix codes, the normalized version of this quantity was proposed by Campbell in 1965 as a generalized average length. We then use the one-shot bounds to analyze the large deviations (reliability function) and small deviations (normal approximation) of the asymptotic fundamental limit in the case of memoryless sources. In contrast to other approaches based on the method of types or the Berry-Esséen inequality, we are able to deal with sources with infinite alphabets.

This paper gives non-asymptotic converse bounds on the cumulant generating function of the encoded lengths in variable-rate lossy compression and in variable-to-fixed channel coding. The results are given in terms of the Rényi mutual information and the d-tilted Rényi entropy. We also illustrate the application of the non-asymptotic bounds to obtain strong converses.

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast which arises between the binary-alphabet and larger-alphabet settings. This is surprising in some instances, since characterizations for the larger-alphabet settings do not generalize their binary-alphabet counterparts. For example, we show that f-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, despite contrary claims in the literature.

We consider a natural measure of the benefit of side information: the reduction in optimal estimation risk when side information is available to the estimator. When such a measure satisfies a natural data processing property, and the source alphabet has cardinality greater than two, we show that it is uniquely characterized by the optimal estimation risk under logarithmic loss, and the corresponding measure is equal to mutual information. Further, when the source alphabet is binary, we characterize the only admissible forms the measure of predictive benefit can assume. These results unify many causality measures in the literature as instantiations of directed information, and present a natural axiomatic characterization of mutual information without requiring the sum or recursivity property.

Multiple reads of the same Flash memory cell with distinct word-line voltages provide enhanced precision for LDPC decoding. In this paper, the word-line voltages are optimized by maximizing the mutual information (MI) of the quantized channel. The enhanced precision from a few additional reads allows frame error rate (FER) performance to approach that of full-precision soft information and enables an LDPC code to significantly outperform a BCH code. A constant-ratio constraint provides a significant simplification in the optimization with no noticeable loss in performance. For a well-designed LDPC code, the quantization that maximizes the mutual information also minimizes the FER in our simulations. However, for an example LDPC code with a high error floor caused by small absorbing sets, the MMI quantization does not provide the lowest frame error rate. The best quantization in this case introduces more erasures than would be optimal for the channel MI in order to mitigate the absorbing sets of the poorly designed code. The paper also identifies a trade-off in LDPC code design when decoding is performed with multiple precision levels; the best code at one level of precision will typically not be the best code at a different level of precision.

We pose a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let Xnbe independent identically distributed Bernoulli(1/2), and let Yn be the result of passing Xnthrough a memoryless binary symmetric channel with crossover probability α. For any Boolean function b : {0, 1}n→ {0, 1}, we conjecture that I(b(Xn); Yn) ≤ 1 - H(α). While the conjecture remains open, we provide substantial evidence supporting its validity. Connections are also made to discrete isoperimetric inequalities.

We consider the classical two-encoder multiterminal source coding problem where distortion is measured under logarithmic loss. We provide a single-letter description of the achievable rate distortion region for all discrete memoryless sources with finite alphabets. By doing so, we also give the rate distortion region for the$m$-encoder CEO problem (also under logarithmic loss). Several applications and examples are given.

Consider a connected network of n nodes that all wish to recover k desired packets. Each node begins with a subset of the desired packets and exchanges coded packets with its neighbors. This paper provides necessary and sufficient conditions that characterize the set of all transmission strategies that permit every node to ultimately learn (recover) all k packets. When the network satisfies certain regularity conditions and packets are randomly distributed, this paper provides tight concentration results on the number of transmissions required to achieve universal recovery. For the case of a fully connected network, a polynomial-time algorithm for computing an optimal transmission strategy is derived. An application to secrecy generation is discussed.

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast that arises between the binary-alphabet and larger alphabet settings. This is surprising in some instances, since characterizations for the larger alphabet settings do not generalize their binary-alphabet counterparts. In particular, we show that f-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that Kullback-Leibler (KL) divergence is the unique Bregman divergence, which is also an f-divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence, which is invariant to statistically sufficient transformations of the data, even when nondecomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three.

The problem of performing similarity queries on compressed data is considered. We study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on compressed data. For a Gaussian source and quadratic similarity criterion, we show that queries can be answered reliably if and only if the compression rate exceeds a given threshold - the identification rate - which we explicitly characterize. When compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that the identification rate is at most that of a Gaussian source with the same variance. Therefore, as with classical compression, the Gaussian source requires the largest compression rate. Moreover, a scheme is described that attains this maximal rate for any source distribution.

An intuitive outer bound for the multiterminal source coding problem is given. The proposed bound explicitly couples the rate distortion functions for each source and correlation measures which derive from a “strong” data processing inequality. Unlike many standard outer bounds, the proposed bound is not parameterized by a continuous family of auxiliary random variables, but instead only requires maximizing two ratios of divergences which do not depend on the distortion functions under consideration.

In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to PX× PY, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions PXand PY. In addition, the scheme achieving this exponent is universal, i.e. does not depend on PX, PY.

We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let Xnbe i.i.d. Bernoulli(l/2), and let Ynbe the result of passing Xnthrough a memoryless binary symmetric channel with crossover probability α. For any Boolean function b : {0, l}n→ {0,1}, we conjecture that I(b(Xn);Yn) ≤ 1 - H (α). While the conjecture remains open, we provide substantial evidence supporting its validity.

Consider a memoryless degraded broadcast channel (DBC) in which the channel output is a single-letter function of the channel input and the channel noise. As examples, for the Gaussian broadcast channel (BC), this single-letter function is real scalar addition and for the binary-symmetric BC, this single-letter function is modulo-two addition. This paper identifies several classes of discrete memoryless DBCs for which a relatively simple encoding scheme, which we call natural encoding, achieves capacity. Natural encoding (NE) combines symbols from independent codebooks (one for each receiver) using the same single-letter function that adds distortion to the channel. The alphabet size of each NE codebook is bounded by that of the channel input. This paper also defines the input-symmetric DBC, introduces permutation encoding for the input-symmetric DBC, and proves its optimality. Because it is a special case of permutation encoding, NE is capacity achieving for the two-receiver group-operation DBC. Combining the broadcast Z channel and group-operation DBC results yields a proof that NE is also optimal for the discrete multiplication DBC. Along the way, the paper also provides explicit parametric expressions for the two-receiver binary-symmetric DBC and broadcast Z channel.

The complementary problems of masking and amplifying channel state information in the Gel'fand-Pinsker channel have recently been solved by Merhav and Shamai, and Kim et al., respectively. In this paper, we study a related source coding problem. Specifically, we consider the two-encoder source coding setting where one source is to be amplified, while the other source is to be masked. In general, there is a tension between these two objectives which is characterized by the amplification-masking tradeoff. In this paper, we give a single-letter description of this tradeoff. We apply this result, together with a recent theorem by Courtade and Weissman on multiterminal source coding, to solve a fundamental entropy characterization problem.

We consider the two-encoder multiterminal source coding problem subject to distortion constraints computed under logarithmic loss. We provide a single-letter description of the achievable rate distortion region for arbitrarily correlated sources with finite alphabets. In doing so, we also give the rate distortion region for the CEO problem under logarithmic loss. Notably, the Berger-Tung inner bound is tight in both settings.

High-capacity NAND flash memory can achieve high density storage by using multi-level cells (MLC) to store more than one bit per cell. Although this larger storage capacity is certainly beneficial, the increased density also increases the raw bit error rate (BER), making powerful error correction coding necessary. Traditional flash memories employ simple algebraic codes, such as BCH codes, that can correct a fixed, specified number of errors. This paper investigates the application of low-density parity-check (LDPC) codes which are well known for their ability to approach capacity in the AWGN channel. We obtain soft information for the LDPC decoder by performing multiple cell reads with distinct word-line voltages. The values of the word-line voltages (also called reference voltages) are optimized by maximizing the mutual information between the input and output of the multiple-read channel. Our results show that using this soft information in the LDPC decoder provides a significant benefit and enables us to outperform BCH codes over a range of block error rates.

In this paper, we consider a class of multiterminal source coding problems, each subject to distortion constraints computed using a specific, entropy-based, distortion measure. We provide the achievable rate distortion region for two cases and, in so doing, we demonstrate a relationship between the lossy multiterminal source coding problems with our specific distortion measure and (1) the canonical Slepian-Wolf lossless distributed source coding network, and (2) the Ahlswede-Körner-Wyner source coding with side information problem in which only one of the sources is recovered losslessly.

For a block-fading channel, this paper optimizes the allocation of redundancy between packet-level erasure coding (which provides additional packets to compensate for packet loss) and physical layer channel coding (which lowers the probability of packet loss). After some manipulation, standard optimization techniques determine the trade-off between the amount of packet-level erasure coding and physical-layer channel coding that minimizes the transmit power required to provide reliable communication. Our results indicate that the optimal combination of packet-level erasure coding and physical-layer coding provides a significant benefit over pure physical-layer coding when no form of channel diversity is present within a packet transmission. However, the benefit of including packet-level erasure coding diminishes as more diversity becomes available within a packet transmission. Even with no diversity within a packet transmission, this paper shows that as the total redundancy becomes large the optimal redundancy for packet-level erasure coding reaches a limit while the optimal redundancy for physical-layer coding continues to increase. Hence providing limitless redundancy at the packet-level with rateless codes such as fountain codes is not the best use of limitless redundancy for block-fading channels.

Rateless coding ensures reliability by providing ever-increasing redundancy, traditionally at the packet level (i.e. the application layer) through erasure coding. This paper explores whether additional redundancy for wireless channels is most helpful at the packet level through erasure coding or at the physical layer through lower-rate channel coding. This cross-layer trade-off is explored in a traditional wireless setting where the communication of a message consisting of a fixed number of packets takes place over a Rayleigh fading channel. The examined scenarios include both a single receiver and multiple cooperating receivers allowing the results to be extended to situations where selection diversity is available in the system. For several interesting scenarios, this paper determines the optimal trade-off between the amount of packet-level erasure coding and physical-layer channel coding required to provide reliable communication over the widest range of operating SNR's. Our results indicate that packet-level erasure coding can provide a significant benefit when no other form of diversity is available. In many cases, the amount of redundancy that should be allocated to such erasure coding is nearly constant, and further redundancy (i.e. any rateless coding) should be applied to the physical layer.