Loïc Fosse, Frederic Bechet, Benoit Favre, Géraldine Damnati, Gwénolé Lecorvé, Maxime Darrin, Philippe Formont, Pablo Piantanida. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Figurative language (e.g., irony, hyperbole, understatement) is ubiquitous in human communication, resulting in utterances where the literal and the intended meanings do not match. The Rational Speech Act (RSA) framework, which explicitly models speaker intentions, is the most widespread theory of probabilistic pragmatics, but existing implementations are either unable to account for figurative expressions or require modeling the implicit motivations for using figurative language (e.g., to express joy or annoyance) in a setting-specific way. In this paper, we introduce the Rhetorical-Strategy-Aware RSA (RSA)² framework which models figurative language use by considering a speaker’s employed rhetorical strategy. We show that (RSA)² enables human-compatible interpretations of non-literal utterances without modeling a speaker’s motivations for being non-literal. Combined with LLMs, it achieves state-of-the-art performance on the ironic split of PragMega+, a new irony interpretation dataset introduced in this study.

As AI systems take on collaborative roles, they must reason about shared goals and beliefs-not just generate fluent language.The Rational Speech Act (RSA) framework offers a principled approach to pragmatic reasoning, but existing extensions face challenges in scaling to multi-turn, collaborative scenarios.In this paper, we introduce Collaborative Rational Speech Act (CRSA), an information-theoretic (IT) extension of RSA that models multi-turn dialog by optimizing a gain function adapted from rate-distortion theory.This gain is an extension of the gain model that is maximized in the original RSA model but takes into account the scenario in which both agents in a conversation have private information and produce utterances conditioned on the dialog.We demonstrate the effectiveness of CRSA on referential games and template-based doctor-patient dialogs in the medical domain.Empirical results show that CRSA yields more consistent, interpretable, and collaborative behavior than existing baselines, paving the way for more pragmatically competent language agents.

Casting complex inputs into tractable representations is a critical step across various fields. Diverse embedding models emerge from differences in architectures, loss functions, input modalities and datasets, each capturing unique aspects of the input. Multi-teacher distillation leverages this diversity to enrich representations but often remains tailored to specific tasks. We introduce a task-agnostic framework based on a ``majority vote" objective function. We demonstrate that this function is bounded by the mutual information between the student and the teachers' embeddings, leading to a task-agnostic distillation loss that eliminates dependence on task-specific labels or prior knowledge. Comprehensive evaluations across text, vision models, and molecular modeling show that our method effectively leverages teacher diversity, resulting in representations enabling better performance for a wide range of downstream tasks such as classification, clustering, or regression. Additionally, we train and release state-of-the-art embedding models, enhancing downstream performance in various modalities.

Progress in a research field can be hard to assess, in particular when many concurrent methods are proposed in a short period of time. This is the case in digital pathology, where many foundation models have been released recently to serve as feature extractors for tile-level images, being used in a variety of downstream tasks, both for tile- and slide-level problems. Benchmarking available methods then becomes paramount to get a clearer view of the research landscape. In particular, in critical domains such as healthcare, a benchmark should not only focus on evaluating downstream performance, but also provide insights about the main differences between methods, and importantly, further consider uncertainty and robustness to ensure a reliable usage of proposed models. For these reasons, we introduce THUNDER, a tile-level benchmark for digital pathology foundation models, allowing for efficient comparison of many models on diverse datasets with a series of downstream tasks, studying their feature spaces and assessing the robustness and uncertainty of predictions informed by their embeddings. THUNDER is a fast, easy-to-use, dynamic benchmark that can already support a large variety of state-of-the-art foundation, as well as local user-defined models for direct tile-based comparison. In this paper, we provide a comprehensive comparison of 23 foundation models on 16 different datasets covering diverse tasks, feature analysis, and robustness. The code for THUNDER is publicly available at https://github.com/MICS-Lab/thunder.

Current sparse neural information retrieval (IR) methods, and to a lesser extent more traditional models such as BM25, do not take into account the document collection and the complex interplay between different term weights when representing a single document. In this paper, we show how the Rational Speech Acts (RSA), a linguistics framework used to minimize the number of features to be communicated when identifying an object in a set, can be adapted to the IR case - and in particular to the high number of potential features (here, tokens). RSA dynamically modulates token-document interactions by considering the influence of other documents in the dataset, better contrasting document representations. Experiments show that incorporating RSA consistently improves multiple sparse retrieval models and achieves state-of-the-art performance on out-of-domain datasets from the BEIR benchmark.

Membership inference attacks (MIA) can reveal whether a particular data point was part of the training dataset, potentially exposing sensitive information about individuals. This article provides theoretical guarantees by exploring the fundamental statistical limitations associated with MIAs on machine learning models at large. More precisely, we first derive the statistical quantity that governs the effectiveness and success of such attacks. We then theoretically prove that in a non-linear regression setting with overfitting learning procedures, attacks may have a high probability of success. Finally, we investigate several situations for which we provide bounds on this quantity of interest. Interestingly, our findings indicate that discretizing the data might enhance the learning procedure's security. Specifically, it is demonstrated to be limited by a constant, which quantifies the diversity of the underlying data distribution. We illustrate those results through simple simulations.

We analyze to what extent final users can infer information about the level of protection of their data when the data obfuscation mechanism is a priori unknown to them (the so-called “black-box” scenario). In particular, we explore four notions of differential privacy, namely local/central "-DP/Renyi- ´ DP. On the one hand, we prove that, without any assumption on the underlying distributions, it is not possible to have an algorithm able to infer the level of data protection with provable guarantees. On the other hand, we demonstrate that, under reasonable assumptions (namely Lipschitzness of the involved densities on a closed interval), such guarantees exist for the local versions and can be achieved by a simple histogrambased estimator. We validate our results experimentally and note that, in two particularly well behaved distributions (namely the Laplace and the Gaussian noise), our method performs better than expected, in the sense that in practice the number of samples needed to achieve the desired confidence is smaller than the theoretical bound, and the estimate of ∊ is more precise than predicted.

Out-of-distribution (OOD) detection is a rapidly growing field due to new robustness and security requirements driven by an increased number of AI-based systems. Existing OOD textual detectors often rely on anomaly scores (\textit{e.g.}, Mahalanobis distance) computed on the embedding output of the last layer of the encoder. In this work, we observe that OOD detection performance varies greatly depending on the task and layer output. More importantly, we show that the usual choice (the last layer) is rarely the best one for OOD detection and that far better results can be achieved, provided that an oracle selects the best layer. We propose a data-driven, unsupervised method to leverage this observation to combine layer-wise anomaly scores. In addition, we extend classical textual OOD benchmarks by including classification tasks with a more significant number of classes (up to 150), which reflects more realistic settings. On this augmented benchmark, we show that the proposed post-aggregation methods achieve robust and consistent results comparable to using the best layer according to an oracle while removing manual feature selection altogether.

Scientific peer review is essential for the quality of academic publications.However, the increasing number of paper submissions to conferences has strained the reviewing process.This surge poses a burden on area chairs who have to carefully read an ever-growing volume of reviews and discern each reviewer's main arguments as part of their decision process.In this paper, we introduce GLIMPSE, a summarization method designed to offer a concise yet comprehensive overview of scholarly reviews.Unlike traditional consensus-based methods, GLIMPSE extracts both common and unique opinions from the reviews.We introduce novel uniqueness scores based on the Rational Speech Act framework to identify relevant sentences in the reviews.Our method aims to provide a pragmatic glimpse into all reviews, offering a balanced perspective on their opinions.Our experimental results with both automatic metrics and human evaluation show that GLIMPSE generates more discriminative summaries than baseline methods in terms of human evaluation while achieving comparable performance with these methods in terms of automatic metrics.

Assessing the quality of summarizers poses significant challenges-gold summaries are hard to obtain and their suitability depends on the use context of the summarization system.Who is the user of the system, and what do they intend to do with the summary?In response, we propose a novel task-oriented evaluation approach that assesses summarizers based on their capacity to produce summaries while preserving task outcomes.We theoretically establish both a lower and upper bound on the expected error rate of these tasks, which depends on the mutual information between source texts and generated summaries.We introduce COSMIC, a practical implementation of this metric, and demonstrate its strong correlation with human judgment-based metrics, as well as its effectiveness in predicting downstream task performance.Comparative analyses against established metrics like BERTScore and ROUGE highlight the competitive performance of COSMIC.

This research delves into a scenario where a malicious actor can manipulate data samples using a multi-armed attack strategy, providing them with multiple ways to introduce noise into the data sample. Our central objective is to protect the data by detecting any alterations to the input. We approach this defensive strategy with utmost caution, operating in an environment where the defender possesses significantly less information compared to the attacker. Specifically, the defender is unable to utilize any data samples for training a defense model or verifying the integrity of the channel. Instead, the defender relies exclusively on a set of pre-existing detectors readily available "off the shelf." To tackle this challenge, we derive an innovative information-theoretic defense approach that optimally aggregates the decisions made by these detectors, eliminating the need for any training data. We further explore a practical use-case scenario for empirical evaluation, where the attacker possesses a pre-trained classifier and launches well-known adversarial attacks against it. Our experiments highlight the effectiveness of our proposed solution, even in scenarios that deviate from the optimal setup.

This paper presents a two-stage Multiple-Model Compression (MMC) approach for sampled electrical waveforms. To limit latency, the processing is window-based, with a window length commensurate to the electrical period. For each window, the first stage compares several parametric models to get a coarse representation of the samples. The second stage then compares different residual compression techniques to minimize the norm of the reconstruction error. The allocation of the rate budget among the two stages is optimized. The proposed MMC approach provides better signal-to-noise ratios than state-of-the-art solutions on periodic and transient waveforms.

Misclassification detection is an important problem in machine learning, as it allows for the identification of instances where the model's predictions are unreliable. However, conventional uncertainty measures such as Shannon entropy do not provide an effective way to infer the real uncertainty associated with the model's predictions. In this paper, we introduce a novel data-driven measure of uncertainty relative to an observer for misclassification detection. By learning patterns in the distribution of soft-predictions, our uncertainty measure can identify misclassified samples based on the predicted class probabilities. Interestingly, according to the proposed measure, soft-predictions corresponding to misclassified instances can carry a large amount of uncertainty, even though they may have low Shannon entropy. We demonstrate empirical improvements over multiple image classification tasks, outperforming state-of-the-art misclassification detection methods.

This paper tackles the challenge of detecting unreliable behavior in regression algorithms, which may arise from intrinsic variability (e.g., aleatoric uncertainty) or modeling errors (e.g., model uncertainty). First, we formally introduce the notion of unreliability in regression, i.e., when the output of the regressor exceeds a specified discrepancy (or error). Then, using powerful tools for probabilistic modeling, we estimate the discrepancy density, and we measure its statistical diversity using our proposed metric for statistical dissimilarity. In turn, this allows us to derive a data-driven score that expresses the uncertainty of the regression outcome. We show empirical improvements in error detection for multiple regression tasks, consistently outperforming popular baseline approaches, and contributing to the broader field of uncertainty quantification and safe machine learning systems.

Embedders play a central role in machine learning, projecting any object into numerical representations that can, in turn, be leveraged to perform various downstream tasks. The evaluation of embedding models typically depends on domain-specific empirical approaches utilizing downstream tasks, primarily because of the lack of a standardized framework for comparison. However, acquiring adequately large and representative datasets for conducting these assessments is not always viable and can prove to be prohibitively expensive and time-consuming. In this paper, we present a unified approach to evaluate embedders. First, we establish theoretical foundations for comparing embedding models, drawing upon the concepts of sufficiency and informativeness. We then leverage these concepts to devise a tractable comparison criterion (information sufficiency), leading to a task-agnostic and self-supervised ranking procedure. We demonstrate experimentally that our approach aligns closely with the capability of embedding models to facilitate various downstream tasks in both natural language processing and molecular biology. This effectively offers practitioners a valuable tool for prioritizing model trials.

Federated Learning is expected to provide strong privacy guarantees, as only gradients or model parameters but no plain text training data is ever exchanged either between the clients or between the clients and the central server. In this paper, we challenge this claim by introducing a simple but still very effective membership inference attack algorithm, which relies only on a single training step. In contrast to the popular honest-but-curious model, we investigate a framework with a dishonest central server. Our strategy is applicable to models with ReLU activations and uses the properties of this activation function to achieve perfect accuracy. Empirical evaluation on visual classification tasks with MNIST, CIFAR10, CIFAR100 and CelebA datasets show that our method provides perfect accuracy in identifying one sample in a training set with thousands of samples. Occasional failures of our method lead us to discover duplicate images in the CIFAR100 and CelebA datasets

Generative Adversarial Networks (GANs) have been widely used for generating synthetic data for cases where there is a limited size real-world data set or when data holders are unwilling to share their data samples. Recent works showed that GANs, due to overfitting and memorization, might leak information regarding their training data samples. This makes GANs vulnerable to Membership Inference Attacks (MIAs). Several defense strategies have been proposed in the literature to mitigate this privacy issue. Unfortunately, defense strategies based on differential privacy are proven to reduce extensively the quality of the synthetic data points. On the other hand, more recent frameworks such as PrivGAN and PAR-GAN are not suitable for small-size training data sets. In the present work, the overfitting in GANs is studied in terms of the discriminator, and a more general measure of overfitting based on the Bhattacharyya coefficient is defined. Then, inspired by Fano’s inequality, our first defense mechanism against MIAs is proposed. This framework, which requires only a simple modification in the loss function of GANs, is referred to as the maximum entropy GAN or MEGAN and significantly improves the robustness of GANs to MIAs. As a second defense strategy, a more heuristic model based on minimizing the information leaked from the generated samples about the training data points is presented. This approach is referred to as mutual information minimization GAN (MIMGAN) and uses a variational representation of the mutual information to minimize the information that a synthetic sample might leak about the whole training data set. Applying the proposed frameworks to some commonly used data sets against state-of-the-art MIAs reveals that the proposed methods can reduce the accuracy of the adversaries to the level of random guessing accuracy with a small reduction in the quality of the synthetic data samples.

Neural machine translation (NMT) has become the de-facto standard in real-world machine translation applications.However, NMT models can unpredictably produce severely pathological translations, known as hallucinations, that seriously undermine user trust.It becomes thus crucial to implement effective preventive strategies to guarantee their proper functioning.In this paper, we address the problem of hallucination detection in NMT by following a simple intuition: as hallucinations are detached from the source content, they exhibit cross-attention patterns that are statistically different from those of good quality translations.We frame this problem with an optimal transport formulation and propose a fully unsupervised, plug-in detector that can be used with any attention-based NMT model.Experimental results show that our detector not only outperforms all previous model-based detectors, but is also competitive with detectors that employ external models trained on millions of samples for related tasks such as quality estimation and cross-lingual sentence similarity.

We tackle the Few-Shot Open-Set Recognition (FSOSR) problem, i.e. classifying instances among a set of classes for which we only have a few labeled samples, while simultaneously detecting instances that do not belong to any known class. We explore the popular transductive setting, which leverages the unlabelled query instances at inference. Motivated by the observation that existing transductive methods perform poorly in open-set scenarios, we propose a generalization of the maximum likelihood principle, in which latent scores down-weighing the influence of potential outliers are introduced alongside the usual parametric model. Our formulation embeds supervision constraints from the support set and additional penalties discouraging overconfident predictions on the query set. We proceed with a block-coordinate descent, with the latent scores and parametric model co-optimized alternately, thereby benefiting from each other. We call our resulting formulation Open-Set Likelihood Optimization (OSLO). OSLO is interpretable and fully modular; it can be applied on top of any pre-trained model seamlessly. Through extensive experiments, we show that our method surpasses existing inductive and transductive methods on both aspects of open-set recognition, namely inlier classification and outlier detection. Code is available at https://github.com/ebennequin/few-shot-open-set.

Pierre Colombo, Victor Pellegrain, Malik Boudiaf, Myriam Tami, Victor Storchan, Ismail Ayed, Pablo Piantanida. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Implementing effective control mechanisms to ensure the proper functioning and security of deployed NLP models, from translation to chatbots, is essential.A key ingredient to ensure safe system behaviour is Out-Of-Distribution (OOD) detection, which aims to detect whether an input sample is statistically far from the training distribution.Although OOD detection is a widely covered topic in classification tasks, most methods rely on hidden features output by the encoder.In this work, we focus on leveraging soft-probabilities in a black-box framework, i.e. we can access the soft-predictions but not the internal states of the model.Our contributions include: (i) RAINPROOF a Relative informAItioN Projection OOD detection framework; and (ii) a more operational evaluation setting for OOD detection.Surprisingly, we find that OOD detection is not necessarily aligned with task-specific measures.The OOD detector may filter out samples well processed by the model and keep samples that are not, leading to weaker performance.Our results show that RAINPROOF provides OOD detection methods more aligned with task-specific performance metrics than traditional OOD detectors.

Adversarial robustness has become a topic of growing interest in machine learning since it was observed that neural networks tend to be brittle. We propose an information-geometric formulation of adversarial defense and introduce Fire, a new Fisher-Rao regularization for the categorical cross-entropy loss, which is based on the geodesic distance between the softmax outputs corresponding to natural and perturbed input features. Based on the information-geometric properties of the class of softmax distributions, we derive an explicit characterization of the Fisher-Rao Distance (FRD) for the binary and multiclass cases, and draw some interesting properties as well as connections with standard regularization metrics. Furthermore, we verify on a simple linear and Gaussian model, that all Pareto-optimal points in the accuracy-robustness region can be reached by Fire while other state-of-the-art methods fail. Empirically, we evaluate the performance of various classifiers trained with the proposed loss on standard datasets, showing up to a simultaneous 1% of improvement in terms of clean and robust performances while reducing the training time by 20% over the best-performing methods.

Assessing the quality of natural language generation (NLG) systems through human annotation is very expensive. Additionally, human annotation campaigns are time-consuming and include non-reusable human labour. In practice, researchers rely on automatic metrics as a proxy of quality. In the last decade, many string-based metrics (e.g., BLEU or ROUGE) have been introduced. However, such metrics usually rely on exact matches and thus, do not robustly handle synonyms. In this paper, we introduce InfoLM a family of untrained metrics that can be viewed as a string-based metric that addresses the aforementioned flaws thanks to a pre-trained masked language model. This family of metrics also makes use of information measures allowing the possibility to adapt InfoLM to different evaluation criteria. Using direct assessment, we demonstrate that InfoLM achieves statistically significant improvement and two figure correlation gains in many configurations compared to existing metrics on both summarization and data2text generation tasks.

One of the main concerns about fairness in machine learning (ML) is that, in order to achieve it, one may have to trade off some accuracy. To overcome this issue, Hardt et al. proposed the notion of equality of opportunity (EO), which is compatible with maximal accuracy when the target label is deterministic with respect to the input features. In the probabilistic case, however, the issue is more complicated: It has been shown that under differential privacy constraints, there are data sources for which EO can only be achieved at the total detriment of accuracy, in the sense that a classifier that satisfies EO cannot be more accurate than a trivial (random guessing) classifier. In our paper we strengthen this result by removing the privacy constraint. Namely, we show that for certain data sources, the most accurate classifier that satisfies EO is a trivial classifier. Furthermore, we study the trade-off between accuracy and EO loss (opportunity difference), and provide a sufficient condition on the data source under which EO and non-trivial accuracy are compatible.

When working with textual data, a natural application of disentangled representations is fair classification where the goal is to make predictions without being biased (or influenced) by sensitive attributes that may be present in the data (e.g., age, gender or race).Dominant approaches to disentangle a sensitive attribute from textual representations rely on learning simultaneously a penalization term that involves either an adversarial loss (e.g., a discriminator) or an information measure (e.g., mutual information).However, these methods require the training of a deep neural network with several parameter updates for each update of the representation model.As a matter of fact, the resulting nested optimization loop is both time consuming, adding complexity to the optimization dynamic, and requires a fine hyperparameter selection (e.g., learning rates, architecture).In this work, we introduce a family of regularizers for learning disentangled representations that do not require training.These regularizers are based on statistical measures of similarity between the conditional probability distributions with respect to the sensitive attributes.Our novel regularizers do not require additional training, are faster and do not involve additional tuning while achieving better results both when combined with pretrained and randomly initialized text encoders.

The use of personal data for training machine learning systems comes with a privacy threat and measuring the level of privacy of a model is one of the major challenges in machine learning today. Identifying training data based on a trained model is a standard way of measuring the privacy risks induced by the model. We develop a novel approach to address the problem of membership inference in pattern recognition models, relying on information provided by adversarial examples. The strategy we propose consists of measuring the magnitude of a perturbation necessary to build an adversarial example. Indeed, we argue that this quantity reflects the likelihood of belonging to the training data. Extensive numerical experiments on multivariate data and an array of state-of-the-art target models show that our method performs comparable or even outperforms state-of-the-art strategies, but without requiring any additional training samples.

This paper studies the problem of designing a quantizer (encoder) for the task of distributed detection of independence subject to one-side communication (limited bits) constraints. By exploiting the asymptotic performance limits as an objective to train a quantization scheme, we propose an algorithm that addresses an info-max problem for this lossy compression task. Tools from machine learning are incorporated to facilitate our data-driven optimization. Experiments on synthetic data support our design principle and approximations, expressing that the devised solutions are effective in compressing data while preserving the relevant information for the underlying task of testing against independence.

Mutual Information (MI) has been widely used as a loss regularizer for training neural networks. This has been particularly effective when learn disentangled or compressed representations of high dimensional data. However, differential entropy (DE), another fundamental measure of information, has not found widespread use in neural network training. Although DE offers a potentially wider range of applications than MI, off-the-shelf DE estimators are either non differentiable, computationally intractable or fail to adapt to changes in the underlying distribution. These drawbacks prevent them from being used as regularizers in neural networks training. To address shortcomings in previously proposed estimators for DE, here we introduce KNIFE, a fully parameterized, differentiable kernel-based estimator of DE. The flexibility of our approach also allows us to construct KNIFE-based estimators for conditional (on either discrete or continuous variables) DE, as well as MI. We empirically validate our method on high-dimensional synthetic data and further apply it to guide the training of neural networks for real-world tasks. Our experiments on a large variety of tasks, including visual domain adaptation, textual fair classification, and textual fine-tuning demonstrate the effectiveness of KNIFE-based estimation. Code can be found at https://github.com/g-pichler/knife.

As the number of AI systems keeps growing, it is fundamental to implement and develop efficient control mechanisms to ensure the safe and proper functioning of machine learning (ML) systems. Reliable out-of-distribution (OOD) detection aims to detect test samples that are statistically far from the training distribution, as they might cause failures of in-production systems. In this paper, we propose a new detector called TRUSTED. Different from previous works, TRUSTED key components (i) include a novel OOD score relying on the concept of statistical data depth, (ii) rely on the idea’s full potential that all hidden layers of the network carry information regarding OOD. Our extensive experiments, comparing over 51k model configurations including different checkpoints, seed and various datasets, demonstrate that TRUSTED achieve state-of-the-art performances by producing an improvement of over 3 AUROC points.

The rapid development and expansion of the Internet of Things (IoT) paradigm has drastically increased the collection and exchange of data between sensors and systems, a phenomenon that raises serious privacy concerns in some domains. In particular, smart meters (SMs) share fine-grained electricity consumption of households with utility providers that can potentially violate users’ privacy as sensitive information is leaked through the data. In order to enhance privacy, electricity consumers can exploit the availability of physical resources such as a rechargeable battery (RB) to shape their power demand as dictated by a privacy-cost management unit (PCMU). In this article, we present a novel method to learn the PCMU policy using deep reinforcement learning (DRL). We adopt the mutual information (MI) between the user’s demand load and the masked load seen by the power grid as a reliable and general privacy measure. Unlike previous studies, we model the whole temporal correlation in the data to learn the MI in its general form and use a neural network to estimate the MI-based reward signal to guide the PCMU learning process. This approach is combined with a model-free DRL algorithm known as the deep double${Q}$-learning (DDQL) method. The performance of the complete DDQL-MI algorithm is assessed empirically using an actual SMs data set and compared with simpler privacy measures. Our results show significant improvements over state-of-the-art privacy-aware demand shaping methods.

The problem of variable length and fixed-distortion universal source coding (or D-semifaithful source coding) for stationary and memoryless sources on countably infinite alphabets ($\infty $-alphabets) is addressed in this paper. The main results of this work offer a set of sufficient conditions (from weaker to stronger) to obtain weak minimax universality, strong minimax universality, and corresponding achievable rates of convergences for the worst-case redundancy for the family of stationary memoryless sources whose densities are dominated by an envelope function (or the envelope family) on$\infty $-alphabets. An important implication of these results is that universal D-semifaithful source coding is not feasible for the complete family of stationary and memoryless sources on$\infty $-alphabets. To demonstrate this infeasibility, a sufficient condition for the impossibility is presented for the envelope family. Interestingly, it matches the well-known impossibility condition in the context of lossless (variable-length) universal source coding. More generally, this work offers a simple description of what is needed to achieve universal D-semifaithful coding for a family of distributions$\Lambda $. This reduces to finding a collection of quantizations of the product space at different block-lengths — reflecting the fixed distortion restriction — that satisfy two asymptotic requirements: the first is a universal quantization condition with respect to$\Lambda $, and the second is a vanishing information radius (I-radius) condition for$\Lambda $reminiscent of the condition known for lossless universal source coding.

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size M and the network load R for the networks where a server with N files is connected to H relays (without caches), which in turn are connected to K users equipped with caches of M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some (N, M, H, r) parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.

Pierre Colombo, Pablo Piantanida, Chloé Clavel. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

We show that the way inference is performed in few-shot segmentation tasks has a substantial effect on performances—an aspect often overlooked in the literature in favor of the meta-learning paradigm. We introduce a transductive inference for a given query image, leveraging the statistics of its unlabeled pixels, by optimizing a new loss containing three complementary terms: i) the cross-entropy on the labeled support pixels; ii) the Shannon entropy of the posteriors on the unlabeled query-image pixels; and iii) a global KL-divergence regularizer based on the proportion of the predicted foreground. As our inference uses a simple linear classifier of the extracted features, its computational load is comparable to inductive inference and can be used on top of any base training. Foregoing episodic training and using only standard cross-entropy training on the base classes, our inference yields competitive performances on standard benchmarks in the 1-shot scenarios. As the number of available shots increases, the gap in performances widens: on PASCAL-5i, our method brings about 5% and 6% improvements over the state-of-the-art, in the 5- and 10-shot scenarios, respectively. Furthermore, we introduce a new setting that includes domain shifts, where the base and novel classes are drawn from different datasets. Our method achieves the best performances in this more realistic setting. Our code is freely available online: https://github.com/mboudiaf/RePRI-for-Few-Shot-Segmentation.

A new metric BaryScore to evaluate text generation based on deep contextualized embeddings (e.g., BERT, Roberta, ELMo) is introduced.This metric is motivated by a new framework relying on optimal transport tools, i.e., Wasserstein distance and barycenter.By modelling the layer output of deep contextualized embeddings as a probability distribution rather than by a vector embedding; this framework provides a natural way to aggregate the different outputs through the Wasserstein space topology.In addition, it provides theoretical grounds to our metric and offers an alternative to available solutions (e.g., Mover-Score and BertScore).Numerical evaluation is performed on four different tasks: machine translation, summarization, data2text generation and image captioning.Our results show that BaryScore outperforms other BERT based metrics and exhibits more consistent behaviour in particular for text summarization.

Recent works suggests an interesting interplay between the information flow between inputs features and hidden representations of a learning and the ability of the algorithm to generalize from trained samples to unobserved data. For instance, some of regularization techniques used to control generalization are expected to impact the corresponding information metrics. In this work, we study mutual information in Restricted Boltzmann Machines (RBM) and its relationship with the different regularization techniques. Our results show some evidence on interesting connections between the mutual information (inputs and its representations) with relevant parameters such as: network dimension, matrix norms and dropout probability, which are known to influence the generalization ability of the network. Results are empirically corroborated with a numerical study.

Deep neural networks (DNNs) have shown to perform very well on large scale object recognition problems and lead to widespread use for real-world applications, including situations where DNN are implemented as “black boxes”. A promising approach to secure their use is to accept decisions that are likely to be correct while discarding the others. In this work, we propose DOCTOR, a simple method that aims to identify whether the prediction of a DNN classifier should (or should not) be trusted so that, consequently, it would be possible to accept it or to reject it. Two scenarios are investigated: Totally Black Box (TBB) where only the soft-predictions are available and Partially Black Box (PBB) where gradient-propagation to perform input pre-processing is allowed. Empirically, we show that DOCTOR outperforms all state-of-the-art methods on various well-known images and sentiment analysis datasets. In particular, we observe a reduction of up to 4% of the false rejection rate (FRR) in the PBB scenario. DOCTOR can be applied to any pre-trained model, it does not require prior information about the underlying dataset and is as simple as the simplest available methods in the literature.

Transductive inference is widely used in few-shot learning, as it leverages the statistics of the unlabeled query set of a few-shot task, typically yielding substantially better performances than its inductive counterpart. The current few-shot benchmarks use perfectly class-balanced tasks at inference. We argue that such an artificial regularity is unrealistic, as it assumes that the marginal label probability of the testing samples is known and fixed to the uniform distribution. In fact, in realistic scenarios, the unlabeled query sets come with arbitrary and unknown label marginals. We introduce and study the effect of arbitrary class distributions within the query sets of few-shot tasks at inference, removing the class-balance artefact. Specifically, we model the marginal probabilities of the classes as Dirichlet-distributed random variables, which yields a principled and realistic sampling within the simplex. This leverages the current few-shot benchmarks, building testing tasks with arbitrary class distributions. We evaluate experimentally state-of-the-art transductive methods over 3 widely used data sets, and observe, surprisingly, substantial performance drops, even below inductive methods in some cases. Furthermore, we propose a generalization of the mutual-information loss, based on α-divergences, which can handle effectively class-distribution variations. Empirically, we show that our transductive α-divergence optimization outperforms state-of-the-art methods across several data sets, models and few-shot settings.

A central problem in Binary Hypothesis Testing (BHT) is to determine the optimal tradeoff between the Type I error (referred to as false alarm) and Type II (referred to as miss) error. In this context, the exponential rate of convergence of the optimal miss error probability - as the sample size tends to infinity - given some (positive) restrictions on the false alarm probabilities is a fundamental question to address in theory. Considering the more realistic context of a BHT with a finite number of observations, this letter presents a new non-asymptotic result for the scenario with monotonic (sub-exponential decreasing) restriction on the Type I error probability, which extends the result presented by Strassen in 2009. Building on the use of concentration inequalities, we offer new upper and lower bounds to the optimal Type II error probability for the case of finite observations. Finally, the derived bounds are evaluated and interpreted numerically (as a function of the number samples) for some vanishing Type I error restrictions.

This paper considers the problem of estimating the information leakage of a system in the black-box scenario, i.e. when the system's internals are unknown to the learner, or too complicated to analyze, and the only available information are pairs of input-output data samples, obtained by submitting queries to the system or provided by a third party. The frequentist approach relies on counting the frequencies to estimate the input-output conditional probabilities, however this method is not accurate when the domain of possible outputs is large. To overcome this difficulty, the estimation of the Bayes error of the ideal classifier was recently investigated using Machine Learning (ML) models, and it has been shown to be more accurate thanks to the ability of those models to learn the input-output correspondence. However, the Bayes vulnerability is only suitable to describe one-try attacks. A more general and flexible measure of leakage is the g-vulnerability, which encompasses several different types of adversaries, with different goals and capabilities. We propose a novel approach to perform black-box estimation of the g-vulnerability using ML which does not require to estimate the conditional probabilities and is suitable for a large class of ML algorithms. First, we formally show the learnability for all data distributions. Then, we evaluate the performance via various experiments using k-Nearest Neighbors and Neural Networks. Our approach outperform the frequentist one when the observables domain is large.

This paper addresses the problem of removing from a set of data (here images) a given private information, while still allowing other utilities on the processed data. This is obtained by training concurrently a GAN-like discriminator and an autoencoder. The optimization of the resulting structure involves a novel surrogate of the misclassification probability of the information to remove. Several examples are given, demonstrating that a good level of privacy can be obtained on images at the cost of the introduction of very small artifacts.

We introduce Transductive Infomation Maximization (TIM) for few-shot learning. Our method maximizes the mutual information between the query features and their label predictions for a given few-shot task, in conjunction with a supervision loss based on the support set. Furthermore, we propose a new alternating-direction solver for our mutual-information loss, which substantially speeds up transductive inference convergence over gradient-based optimization, while yielding similar accuracy. TIM inference is modular: it can be used on top of any base-training feature extractor. Following standard transductive few-shot settings, our comprehensive experiments demonstrate that TIM outperforms state-of-the-art methods significantly across various datasets and networks, while used on top of a fixed feature extractor trained with simple cross-entropy on the base classes, without resorting to complex meta-learning schemes. It consistently brings between 2% and 5% improvement in accuracy over the best performing method, not only on all the well-established few-shot benchmarks but also on more challenging scenarios, with domain shifts and larger numbers of classes.

We study the trade-off between secret message (SM) and secret key (SK) rates, simultaneously achievable over a state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes other instances of CSI availability as special cases, and calls for efficient utilization of the state sequence for both reliability and security purposes. An inner bound on the semantic-security (SS) SM-SK capacity region is derived based on a superposition coding scheme inspired by a past work of the authors. The region is shown to attain capacity for a certain class of SD-WTCs. SS is established by virtue of two versions of the strong soft-covering lemma. The derived region yields an improvement upon the previously best known SM-SK trade-off result reported by Prabhakaran et al., and, to the best of our knowledge, upon all other existing lower bounds for either SM or SK for this setup, even if the semantic security requirement is relaxed to weak secrecy. It is demonstrated that our region can be strictly larger than those reported in the preceding works.

This work investigates the general two-user compound Broadcast Channel (BC) in which an encoder wishes to transmit two private messages W1 and W2 to two receivers while being oblivious to the actual channel realizations controlling the communication. The focus is on the characterization of the largest achievable rate region by resorting to more involved encoding and decoding techniques than the usual coding schemes of the standard BC. Involved decoding schemes are first explored, and an achievable rate region is derived based on the principle of Interference Decoding (ID), in which each receiver decodes its intended message and chooses to (non-uniquely) decode, or not, the interfering non-itended message. This decoding scheme is shown to be capacity achieving for a class of non-trivial compound BEC/BSC broadcast channels while the worst-case of Marton's inner bound-based on No Interference Decoding (NID)-fails to achieve the capacity region. Involved encoding schemes are later investigated, and an achievable rate region is derived based on Multiple Description (MD) coding wherin the encoder transmits a common description as well as multiple dedicated private descriptions to the many possible channel realizations of the users. It turns out that MD coding yields larger inner bounds than the single description scheme-Common Description (CD) coding-for a class of compound Multiple Input Single Output Broadcast Channels (MISO BC).

Motivated from the fact that universal source coding on countably infinite alphabets (∞-alphabets) is not feasible, this work introduces the notion of “almost lossless source coding”. Analog to the weak variable-length source coding problem studied by Han (IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1217-1226, Jul. 2000), almost lossless source coding aims at relaxing the lossless block-wise assumption to allow an average per-letter distortion that vanishes asymptotically as the block-length tends to infinity. In this setup, we show on one hand that Shannon entropy characterizes the minimum achievable rate (similarly to the case of finite alphabet sources) while on the other that almost lossless universal source coding becomes feasible for the family of finite-entropy stationary memoryless sources with ∞-alphabets. Furthermore, we study a stronger notion of almost lossless universality that demands uniform convergence of the average per-letter distortion to zero, where we establish a necessary and sufficient condition for the so-called family of “envelope distributions” to achieve it. Remarkably, this condition is the same necessary and sufficient condition needed for the existence of a strongly minimax (lossless) universal source code for the family of envelope distributions. Finally, we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared to the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. This shows that even when lossless universality is feasible, an almost lossless scheme can offer different regimes on the rates of convergence of the (worst case) redundancy versus the (worst case) distortion.

Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.

Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user's local cache memory, even without knowledge of user's later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users' demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the “acyclic index coding converse bound.” This converse bound is proved to be achievable by the Maddah-Ali and Niesen's scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used “composite (index) coding” achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper.

Using information-theoretic tools, this paper establishes a mathematical link between the probability of success of a side-channel attack and the minimum number of queries to reach a given success rate, valid for any possible distinguishing rule and with the best possible knowledge on the attacker's side. This link is a lower bound on the number of queries, which depends on the mutual information between the traces and the secret key. This leads us to derive upper bounds on the mutual information that are as tight as possible and can be easily calculated. It turns out that, in the case of additive white Gaussian noise, the bound on the probability of success of any attack is directly related to the signal-to-noise ratio (SNR). This leads to easy computations and predictions of the success rate for any leakage model.

The problem of fixed-distortion universal source coding (or universal D-semifaithfull source coding) for stationary and memoryless sources on countably infinite alphabets is investigated. The main result of this paper offers sufficient conditions to achieve strong and weak minimax universality for D-semifaithfull source coding of any memoryless source defined by an envelope function on infinite alphabets. It is also shown that universal D-semifaithfull source coding is not feasible for the complete family of memoryless sources. Furthermore, a sufficient condition for impossibility is presented for the family of envelope distributions.

It is a well-known fact that feedback does not increase the capacity of point-to-point memoryless channels, however, its effect in secure communications is not fully understood yet. In this paper, an achievable scheme for the wiretap channel with generalized feedback is presented. This scheme, which uses the feedback signal to generate a shared secret key between the legitimate users, encrypts the message to be sent at the bit level. New capacity results for a class of channels are provided, as well as some new insights into the secret key agreement problem. Moreover, this scheme recovers previously reported rate regions from the literature, and thus it can be seen as a generalization that unifies several results in the field.

This paper investigates a multi-terminal source coding problem under a logarithmic loss fidelity which does not necessarily lead to an additive distortion measure. The problem is motivated by an extension of the information bottleneck method to a multi-source scenario where several encoders have to build cooperatively rate-limited descriptions of their sources in order to maximize information with respect to other unobserved (hidden) sources. More precisely, we study fundamental information-theoretic limits of the so-called: 1) two-way collaborative information bottleneck (TW-CIB) and 2) the collaborative distributed information bottleneck (CDIB) problems. The TW-CIB problem consists of two distant encoders that separately observe marginal (dependent) components X1and X2and can cooperate through multiple exchanges of limited information with the aim of extracting information about hidden variables (Y1, Y2), which can be arbitrarily dependent on (X1, X2). On the other hand, in CDIB, there are two cooperating encoders which separately observe X1and X2and a third node which can listen to the exchanges between the two encoders in order to obtain information about a hidden variable Y. The relevance (figure-of-merit) is measured in terms of a normalized (per-sample) multi-letter mutual information metric (log-loss fidelity), and an interesting tradeoff arises by constraining the complexity of descriptions, measured in terms of the rates needed for the exchanges between the encoders and decoders involved. Inner and outer bounds to the complexity-relevance region of these problems are derived from which optimality is characterized for several cases of interest. Our resulting theoretical complexity-relevance regions are finally evaluated for binary symmetric and Gaussian statistical models, showing theoretical tradeoffs between the complexity-constrained descriptions and their relevance with respect to the hidden variables.

In this paper, we develop the Kalman filter for the identification of bilinear forms. In this framework, the bilinear term is defined with respect to the impulse responses of a spatiotemporal model, which resembles a multiple-input/single-output system. Recently, the identification of such bilinear forms was addressed in terms of the Wiener filter and conventional adaptive algorithms, i.e., least-mean-square and recursive least-squares. In this work, apart from the derivation of the Kalman filter tailored for the identification of bilinear forms, a simplified (i.e., low complexity) version of the algorithm is also presented. Simulation results support the theoretical findings and indicate the good performance of the proposed solutions.

This paper investigates, from information theoretic principles, a learning problem based on the principle that any regularity in a given dataset can be exploited to extract compact features from data, in order to build meaningful representations of a relevant content. We begin by introducing the fundamental tradeoff between the average risk and the model complexity. Interestingly, our formulation allows an information theoretic formulation of the multi-task learning (MTL) problem. Then, we present an iterative algorithm for computing the optimal tradeoffs. Remarkably, empirical results illustrate that there exists an optimal information rate minimizing the excess risk which depends on the nature and the amount of available training data. An application to hierarchical text categorization is also investigated, extending previous works.

Maddah-Ali and Niesen's original coded caching scheme for shared-link broadcast networks is now known to be optimal to within a factor two, and has been applied to other types of networks. For practical reasons, this paper considers that a server communicates to cache-aided users through H intermediate relays. In particular, it focuses on combination networks where each of the K = (rH) users is connected to a r distinct r-subsets of relays. By leveraging the symmetric topology of the network, this paper proposes a novel method to generate multicast messages such that each multicast message sent to each relay is useful for the largest possible subset of users connected to this relay. By numerical evaluations, the proposed scheme is shown to reduce the download time compared to the schemes available in the literature. The idea is then extended to decentralized combination networks, more general relay networks, and combination networks with cache-aided relays and users. Also in these cases the proposed scheme outperforms known ones.

We investigate the problem of sharing (communi-cating) the outcomes of a memoryless source when some of its statistical parameters must be kept private. Privacy is measured in terms of the Bayesian statistical risk according to a desired loss function while the quality of the reconstruction is measured by the average per-letter distortion. We first bound -uniformly over all possible estimators- the expected risk from below. This information-theoretic bound depends on the mutual information between the parameters and the disclosed (noisy) samples. We then present an achievable scheme that guarantees an upper bound on the average distortion while keeping the risk above a desired threshold, even when the length of the sample increases.

The state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) available at the encoder is considered. An inner bound on the trade-off region between admissible secret key (SK) and secret message (SM) rates is provided. The result is derived under the stringent semantic-security metric. Our inner bound recovers the best-known achievability results for either SK generation, SM transmission, or simultaneous execution of both. Since some of these past benchmarks were derived under weaker security metrics, our results imply that an upgrade to semantic-security is possible without inflicting any rate loss. It is shown that for certain instances of the considered SD-WTC, the derived region is strictly larger than the previously best-known SK-SM trade-off region reported by Prabhakaran et al., and that a recently reported SK rate for this setup cannot be achieved.

A grand challenge in representation learning is the development of computational algorithms that learn the different explanatory factors of variation behind high-dimensional data. Encoder models are usually determined to optimize performance on training data when the real objective is to generalize well to other (unseen) data. Although numerical evidence suggests that noise injection at the level of representations might improve the generalization ability of the resulting encoders, an information-theoretic justification of this principle remains elusive. In this work, we derive an upper bound to the so-called generalization gap corresponding to the cross-entropy loss and show that when this bound times a suitable multiplier and the empirical risk are minimized jointly, the problem is equivalent to optimizing the Information Bottleneck objective with respect to the empirical data-distribution. We specialize our general conclusions to analyze the dropout regularization method in deep neural networks, explaining how this regularizer helps to decrease the generalization gap.

This paper investigates the fundamental tradeoff between cache size and download time in the (H, r, M, N) combination network, where a server with N files is connected to H relays (without caches) and each of the K: = Hr users (with caches of size M files) is connected to a different subset of r relays. Existing schemes fall within two categories: either use the uncoded symmetric cache placement originally proposed for the shared-link model and design delivery phase dependent on the network topology, or effectively divide the combination network into H uncoordinated shared-link networks each serving K':= H-1r-1 users; in either case, the placement phase leverages effectively the connectivity of relay s/users. In this paper, a novel strategy is proposed where the coded cache placement is dependent on network topology. The proposed scheme is shown to be information theoretically optimal for large cache size. In addition, when not exactly optimal, the proposed scheme can also outperform existing schemes.

The state-dependent K-user memoryless broadcast channel (BC) with state feedback is investigated. We propose a novel transmission scheme and derive its corresponding achievable rate region, which, compared with some general schemes that deal with feedback, has the advantage of being relatively simple and thus is easy to evaluate. In particular, we show that the proposed scheme achieves the capacity region of the symmetric erasure BC with an arbitrary input alphabet size. For the fading Gaussian BC, numerical results show that the proposed scheme outperforms existing schemes in terms of symmetric rate. Our analysis also proves its optimality at high signal-to-noise ratio, in terms of degrees of freedom.

Consider a source coding problem in presence of two dependent with memory sources (X, Y), for which only X is available at the encoder (referred to Alice). We first study the design of vector quantization for the situation where one of the source outputs, i.e., X, must be transmitted to the receiver (referred to Bob) within a prescribed distortion tolerance as in ordinary source coding. On the other hand, the other source, i.e., Y, has to be kept as secret as possible from the receiver or wiretappers. We next consider the opposite case where Y represents a relevant utility sequence to be reconstructed at Bob while trying to keep information about X secret from an eventual eavesdropper. A practical application involving electric consumption data measured from real houses is finally investigated.

This paper investigates the Multiple Description (MD) Chief Executive Officer (CEO) problem under logarithmic-loss distortion. The setup extends previous work of Courtade and Weissman (2014) by requiring the CEO to obtain a useful reconstruction also from a reduced set of descriptions. A single-letter characterization of the achievable region is derived under a suitable conditional independence assumption. Surprisingly, the resulting rate requirement is in general less than that required to ensure successful typicality decoding of the corresponding description.

The problem of almost lossless universal coding is revisited in this work. We study uniform rate of convergence for distortion and redundancy over a family of envelope distributions. In particular, we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared with the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. Our results show that even when lossless universality is feasible, an almost lossless scheme can still offer different regimes on the rates of convergence of the redundancy versus the distortion.The problem of almost lossless universal coding is revisited in this work. We study uniform rate of convergence for distortion and redundancy over a family of envelope distributions. In particular, we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared with the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. Our results show that even when lossless universality is feasible, an almost lossless scheme can still offer different regimes on the rates of convergence of the redundancy versus the distortion.

This paper investigates a scenario where two distant nodes separately observe memoryless process, namely X1and X2, and can cooperate through multiple exchanges of messages with the goal of enabling a third node to learn “relevant information” (measured in terms of a multi-letter mutual information) about some hidden memoryless process Y, which is arbitrarily dependent on (X1, X2). These interactive exchanges yield an explicit cooperation that helps the third node to identify, from the distributed observations X1and X2, useful features for the inference of Y. An inner and an outer bound to the rate-relevance region of this problem is derived. Optimal characterization of the rate-relevance region under two different conditions on the dependence structures of the involved variables is showed. Also, two examples for Gaussian sources are studied.

This paper studies the tradeoff between the memory size M and the download time / rate R* for networks where a server with N files is connected to H relays (without caches), which in turns are connected to K users equipped with caches of size M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, outer bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly copied in the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well known “acyclic index coding outer bound” results in bounds that are not tight for combination networks with enduser-caches (as opposed to the case without relays) and provides two novel ways to derive the tightest known outer bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived.

The muti-layer information bottleneck (IB) problem, where information is propagated (or successively refined) from layer to layer, is considered. Based on information forwarded by the preceding layer, each stage of the network is required to preserve a certain level of relevance with regards to a specific hidden variable, quantified by the mutual information. The hidden variables and the source can be arbitrarily correlated. The optimal trade-off between rates of relevance and compression (or complexity) is obtained through a singleletter characterization, referred to as the rate-relevance region. Conditions of successive refinabilty are given. Binary source with BSC hidden variables and binary source with BSC/BEC mixed hidden variables are both proved to be successively refinable. We further extend our result to Guassian models. A counterexample of successive refinability is also provided.

The capacity region of the multicast Cognitive InterFerence Channel (CIFC) is investigated. This channel consists of two independent transmitters that wish to multicast two different messages, each to a different set of users. In addition, one of the transmitters-commonly referred to as the cognitive transmitter-has prior non-causal knowledge of both messages to be transmitted. This scenario subsumes some long-standing open problems, such as the interference channel, the broadcast channel, and multicast communications. The aim of this paper is the derivation of optimal interference mitigation techniques under different interference regimes. To this end, two settings, namely the multi-primary CIFC, i.e., M = 1 and N ≥ 1, and its complementary, the multi-secondary CIFC, i.e., N = 1 and M ≥ 1, are investigated as an attempt to build a thorough understanding for the more general multicast CIFC setting. It is shown that, for some interference regimes, well-known coding techniques for the standard CIFC remain still optimal under the constraint of multicasting to multiple users. However, in other interference regimes, capacity achieving coding and decoding schemes prove to be more involved. A careful combination of these coding schemes and new outer bounding techniques allows to characterize the capacity region for several classes of discrete memoryless and Gaussian multicast CIFC under different interference regimes.

Consider the problem where a statistician in a two-node system receives rate-limited information from a transmitter about marginal observations of a memoryless process generated from two possible distributions. Using its own observations, this receiver is required to first identify the legitimacy of its sender by declaring the joint distribution of the process, and then depending on such authentication, it generates adequate reconstruction of the observations, satisfying an average per-letter distortion. The performance of this setup is investigated through the corresponding rate-error-distortion region, describing the tradeoff between: the communication rate, the error exponent induced by the detection, and the distortion incurred by the source reconstruction. In the special case of testing against independence, where the alternative hypothesis implies that the sources are independent, the optimal rate-error-distortion region is characterized. An application example to binary symmetric sources is given subsequently and the explicit expression for the rate-error-distortion region is provided as well. The case of “general hypotheses” is also investigated. A new achievable rate-error-distortion region is derived based on the use of non-asymptotic binning, improving the quality of communicated descriptions. Further improvement of performance in the general case is shown to be possible when the requirement of source reconstruction is relaxed, which stands in contrast to the case of general hypotheses.

In this paper, we explore the three-node multiterminal 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.

The design of scalar quantization for distributed binary decision in presence of an eavesdropper (Eve) is investigated. An encoder/quantizer (Alice) observes a memoryless source and communicate via a public noiseless rate-limited channel with the detector (Bob) who has also access to a correlated analog source. Bob can take advantage of both informations to perform a binary decision on the joint probability law of these observations. Eve is further assumed to have access to a different correlated analog source and perfectly observe the information bits sent by Alice. This paper evaluates the various tradeoffs between the probabilities of error (on the decision) depending on the amount of information leakage from Alice to Eve. The Bhattacharyya distance; one of the distances measuring the difference between two probability distributions; is taken as a criterion to optimize the scalar quantizer subject to a tolerable constraint on the information leakage at the level of Eve. Numerical results for memoryless Gaussian sources demonstrate the performance of the proposed quantization method.

This paper investigates the problem of secret key generation over a wiretap channel when the terminals have access to correlated sources. These sources are independent of the main channel and the users observe them before the transmission takes place. A novel achievable scheme for this model is proposed and is shown to be optimal under certain less noisy conditions. This result improves upon the existing literature where the more stringent condition of degradedness was needed.

The problem of collaborative distributed hypothesis testing is investigated. In this setting, a binary decision is required about the joint distribution of two arbitrary dependent memoryless processes that are sampled at different physical locations (nodes) in the system. Interactive rate-limited communication is allowed between these nodes. Defining two types of error events, the error exponent for an error of the second type is investigated, under a prescribed probability of error of the first type. A general achievable error exponent, as a function of the total available communication resources, is proposed, for the case of two general hypotheses. The special case of testing against independence is revisited for which it is shown that optimality can be attained, as a special case of the general achievable exponent, provided the constraint over the error probability of the first type goes to zero.

This paper investigates the problem of distributed biclustering of memoryless sources and extends previous work [1] to the general case with more than two sources. Given a set of distributed stationary memoryless sources, the encoders' goal is to find rate-limited representations of these sources such that the mutual information between two selected subsets of descriptions (each of them generated by distinct encoders) is maximized. This formulation is fundamentally different from conventional distributed source coding problems since here redundancy among descriptions should actually be maximally preserved. We derive non-trivial outer and inner bounds to the achievable region for this problem and further connect them to the CEO problem under logarithmic loss distortion. Since information-theoretic biclustering is closely related to distributed hypothesis testing against independence, our results are also expected to apply to that problem.

Motivated from the fact that universal source coding on countably infinite alphabets is not feasible, the notion of almost lossless source coding is introduced. This idea -analog to the weak variable-length source coding problem proposed by Han [1]- aims at relaxing the lossless block-wise assumption to allow a distortion that vanishes asymptotically as the block-length goes to infinity1. In this setup, both feasibility and optimality results are derived for the case of memoryless sources defined on countably infinite alphabets. Our results show on one hand that Shannon entropy characterizes the minimum achievable rate (known statistics) while on the other that almost lossless universal source coding becomes feasible for the family of finite entropy stationary and memoryless sources with countably infinite alphabets.

Caching is an efficient way to reduce peak hour network traffic congestion by storing some content at the user's cache without knowledge of later demands. Recently, Maddah-Ali and Niesen proposed a two-phase, placement and delivery phase, coded caching strategy for centralized systems (where coordination among users is possible in the placement phase), and for decentralized systems. This paper investigates the same setup under the assumption that the number of users is larger than the number of files. By using the same uncoded placement strategy of Maddah-Ali and Niesen, a novel coded delivery strategy is proposed to profit from the multicasting opportunities that arise because a file may be demanded by multiple users. The proposed delivery method is proved to be optimal under the constraint of uncoded cache placement for centralized systems with two files. Moreover it is shown to outperform known caching strategies for both centralized and decentralized systems.

Let (X,Y) be a doubly symmetric binary source. For n i.i.d. copies (Xn,Yn) of (X,Y) we show that max[I(f(Xn); g(Yn))]= I(X,Y), where the maximum is over all Boolean functions f, g: {0, 1}n→ {0, 1}. This positively resolves a conjecture published by Kumar and Courtade in 2013.

Caching is an effective way to reduce peak-hour network traffic congestion by storing some contents at user's local cache. Maddah-Ali and Niesen (MAN) initiated a fundamental study of caching systems by proposing a scheme (with uncoded cache placement and linear network coding delivery) that is provably optimal to within a factor 4.7. In this paper, when the cache contents and the user demands are fixed, we connect the caching problem to an index coding problem and show the optimality of the MAN scheme under the conditions that (i) the cache placement phase is restricted to be uncoded (i.e, pieces of the files can only copied into the user's cache), and (ii) the number of users is no more than the number of files. As a consequence, further improvements to the MAN scheme are only possible through the use of coded cache placement.

In this paper, we investigate the fast fading broadcast relay channel (BRC) with one source (macrocell BS), one relay (smallcell BS), and two destinations (mobile users). We assume that the instantaneous channel state information (CSI) is known only at the receivers' side, whereas the relay can obtain a noiseless CSI feedback from the destinations about the source-destination channels (with delay). An inner bound on the capacity region of this channel is derived based on a partial-decode-compress-forward (PDCF) scheme. The main idea is to let the relay decode a significant portion of the source messages and then generate and forward to the receivers some useful side information using both the decoded messages and the CSI feedback. Numerical results show that, thanks to the feedback, the proposed scheme provides a non-negligible gain over conventional decode-forward/compress-forward schemes in terms of sum-rate performance, especially in the high SNR regime. Quite remarkably, we show that overall transmit power of the macrocell network can be significantly reduced owing to the feedback from users to the smallcell BS.

It is well-known that feedback does not increase the capacity of point-to-point memoryless channels, however, its effect in secure communications is not fully understood yet. In this work, an achievable scheme for the wiretap channel with generalized feedback -based on joint source-channel coding- is presented. This scheme recovers previous results, thus it can be seen as a generalization and unification of several results in the field. Additionally, the Gaussian wiretap channel with noisy feedback is analyzed, and the scheme achieves positive secrecy rates even in unfavorable situations where the eavesdropper experiences a much better channel than the legitimate user.

This work investigates the Multicast Cognitive Interference Channel (CIFC) where many secondary users are interested in the same cognitive message. The focus is to study the role that Multiple Description (MD) coding can play under simultaneous transmissions. Though for the very weak, very strong, and mixed very weak/strong interference regimes, resorting to a Common Description (CD) alone is capacity achieving, in the weak interference regime it becomes crucial to resort to a more evolved coding scheme relying on multiple descriptions that could each accommodate differently the interference experienced at the secondary users. A Gaussian example illustrates this claim and various capacity results are likewise reported.

A distributed hypothesis testing (HT) problem is considered, comprising two nodes and a unidirectional communication link. The receiving node is required to make a decision as to the probability distribution in effect. A binning process is used in order to minimize the probability of error, resulting in a new achievable error-exponent. A sub-class of HT problems with general hypotheses is defined, which contains many interesting and relevant problems. The advantage of the binning strategy in comparison to the non-binning approach is demonstrated by means of a binary symmetric example.

The distributed binary hypothesis testing problem with communication and security constraints is investigated. A legitimate statistician (referred to as Bob) is interested in detecting the joint probability distribution of two remotely located sources. To this end, Bob has access to analog and coded data where the later is observed at another node (referred to as Alice) and communicated over a public noise-less channel of finite rate. An eavesdropper (referred to as Eve) has access to the encoded bits. In this framework, we study the tradeoff between the maximum achievable error exponent at Bob, i.e., the minimum Type II error probability for a fixed Type I probability of error, the rate and the equivocation rate. We first derive an achievable rate-exponent-equivocation region. Then, we investigate the special case of testing against independence for which we provide the optimal rate-exponent-equivocation region. An application example to binary sources is also considered.

The rate-distortion regions of cooperative and interactive source coding is studied and characterized in several important special cases. For the general cooperative and interactive three node source coding problem, we present an improved inner bound with respect to the bound derived in [1]. This inner bound is used to characterize the optimal rate-distortion regions of several special cases of three terminal information sharing protocols.

The two-way Information Bottleneck problem, where two nodes exchange information iteratively about two arbitrarily dependent memoryless sources, is considered. Based on the observations and the information exchange, each node is required to extract “relevant information”, measured in terms of the normalized mutual information, from two arbitrarily dependent hidden sources. The optimal trade-off between rates of relevance and complexity, and the number of exchange rounds, is obtained through a single-letter characterization. We further extend the results to the Gaussian case. Applications of our setup arise in the development of collaborative clustering algorithms.

The capacity of the Multicast Cognitive Interference Channel (CIFC), where many primary users are interested in the same message, is investigated. In the light of the existing results on the CIFC, capacity is characterized for the very weak and very strong interference regimes as well as the mixed weak/strong interference scenario through novel inner and outer bounds. Moreover, the capacity regions of the corresponding Gaussian settings are likewise reported.

In this work, we consider incremental redundancy (IR) hybrid automatic repeat request (HARQ), where the transmission rounds are carried over independent block-fading channels. We analyze the multipacket HARQ, where the transmitter allows two different packets to share the same channel block; this stands in contrast with the conventional HARQ, where each packet occupies the entire block. We then optimally assign resources within the block to each packet and in each transmission round. We study superposition coding and time-sharing encoding strategies, and we optimize their parameters to maximize the throughput. Besides the conventional, one-bit (ACK/NACK) signaling we also consider a multibit feedback. We formulate our problem as a Markov decision process (MDP), where the decisions concerning the encoding strategies and their parameters are taken using additional information obtained from the receiver via feedback channel. In the case of the one-bit (ACK/NACK) signaling, the partial state information Markov decision process (PSI-MDP) framework is used to obtain the optimal policies. Numerical examples obtained in a Rayleigh-fading channel indicate that, the proposed multipacket HARQ outperforms the conventional one, by more than 5 dB for high-spectral efficiencies.

The capacity of a class of interference relay channels (IRCs)-the injective semideterministic IRC where the relay can only observe one of the sources-is investigated. We first derive a novel outer bound and two inner bounds which are based on a careful use of each of the available cooperative strategies together with the adequate interference decoding technique. The outer bound extends Telatar and Tse's work, whereas the inner bounds contain several known results in the literature. Our main result is the characterization of the capacity region of the Gaussian class of IRCs studied within a fixed number of bits per dimension, constant gap. The proof relies on the use of the different cooperative strategies in specific SNR regimes due to their complexity. As a matter of fact, this issue reveals the complex nature of the Gaussian IRC where the combination of a single coding scheme for the Gaussian relay and interference channel may not lead to a good coding scheme for this problem, even when the focus is only on capacity within a constant gap over all possible fading statistics.

The problem of communicating a single message to a destination in presence of multiple relay nodes, referred to as cooperative unicast network, is considered. First, we introduce mixed noisy network coding (MNNC) scheme which generalizes noisy network coding where relays are allowed to decode-and-forward (DF) messages while all of them (without exception) transmit noisy descriptions of their observations. These descriptions are exploited at the destination and DF relays aim to decode the transmitted messages while creating full cooperation among the nodes. Moreover, the destination and DF relays can independently select the set of descriptions to be decoded or treated as interference. This concept is further extended to multihopping scenarios, referred to as layered MNNC, where DF relays are organized into disjoint groups representing one hop in the network. For cooperative unicast additive white Gaussian noise (AWGN) networks, we show that-provided DF relays are properly chosen-MNNC improves over all previously established constant gaps to the cut-set bound. Second, we consider the composite cooperative unicast network where the channel parameters are randomly drawn before communication starts and remain fixed during the transmission. Each draw is assumed to be unknown at the source and fully known at the destination but only partly known at the relays. We introduce through MNNC scheme the concept of selective coding strategy (SCS) that enables relays to decide dynamically whether, in addition to communicate noisy descriptions, is possible to decode and forward messages. It is demonstrated through slow-fading AWGN relay networks that SCS clearly outperforms conventional coding schemes.

This paper investigates the secrecy capacity of the wiretap broadcast channel (WBC) with an external eavesdropper where a source wishes to communicate two private messages over a broadcast channel (BC) while keeping them secret from the eavesdropper. We derive a nontrivial outer bound on the secrecy capacity region of this channel which, in absence of security constraints, reduces to the best known outer bound to the capacity of the standard BC. An inner bound is also derived, which follows the behavior of both the best known inner bound for the BC and the wiretap channel. These bounds are shown to be tight for the deterministic BC with a general eavesdropper, the semideterministic BC with a more noisy eavesdropper, and the wiretap BC where users exhibit a less noisiness order between them. Finally, by rewriting our outer bound to encompass the characteristics of parallel channels, we also derive the secrecy capacity region of the product of two inversely less noisy BCs with a more noisy eavesdropper. We illustrate our results by studying the impact of security constraints on the capacity of the WBC with binary erasure and binary symmetric components.

The second-order coding rate of the multiple-input multiple-output (MIMO) quasi-static Rayleigh fading channel is studied. We tackle this problem via an information-spectrum approach and statistical bounds based on recent random matrix theory techniques. We derive a central limit theorem (CLT) to analyze the information density in the regime where the block length n and the number of transmit and receive antennas K and N, respectively, grow simultaneously large. This result leads to the characterization of closed-form upper and lower bounds on the optimal average error probability when the coding rate is within O(1/√(nK)) of the asymptotic capacity.

This paper studies the gains, in terms of served requests, attainable through out-of-band device-to-device (D2D) video exchanges in large cellular networks. A stochastic framework, in which users are clustered to exchange videos, is introduced, considering several aspects of this problem, i.e., the video caching policy, user matching for exchanges, and aspects regarding scheduling and transmissions. A family of admissible protocols is introduced: in each protocol the users are clustered by means of a hard-core point process and, within the clusters, video exchanges take place. Two metrics, quantifying the “local” and “global” fractions of video requests served through D2D are defined, and relevant trade-off regions involving these metrics, as well as quality-of-service constraints, are identified. A simple communication strategy is proposed and analyzed to obtain inner bounds to the trade-off regions and to draw conclusions on the performance attainable through D2D. To this end, the analysis of the time-varying interference that the nodes experience and the tight approximations of its Laplace transform are derived.

In this work we consider incremental redundancy hybrid ARQ (HARQ) transmission of data packets over independent block-fading channels. In HARQ, the transmitter, upon request (NACK), resends the "NACKed" packet in the next available block. Conventionally, the original and retransmitted packets occupy one block, each. In our approach, we allow the transmitter to share the resources between the new and the retransmitted packets. To implement such a multi-packet transmission we consider the superposition coding and the timesharing modulation as possible encoding schemes for simultaneous transmission of both packets. Targeting the maximization of the throughput, we cast the problem into the framework of Markov decision process (MDP), where the decisions about the optimal transmission strategy are taken using information about the state of the receiver in the previous transmissions. Numerical examples obtained in a Rayleigh block-fading channel show that proposed transmission strategy provides notable gains over a conventional HARQ.

The capacity of a class of Interference Relay Channels (IRC) is investigated. We derive a novel outer and three inner bounds which are based on a careful use of all existing cooperative strategies together with the adequate interference decoding technique. Our main result is the necessity of three different cooperative strategies to achieve a constant gap to the capacity for each SNR regime of the Gaussian IRC. Surprisingly enough, this outcome appears to be in contrast with that of the standard Gaussian RC (Relay Channel) where several cooperative strategies yield constant-gap results in all regimes.

The Generalized Markov Lemma has been used in the proofs of several multiterminal source coding theorems for finite alphabets. An alternative approach to extend this result to countable infinite sources is proposed. We establish sufficient conditions to guarantee the joint typicality of reproduction sequences of random descriptions that have not been necessarily generated from the product of probability measures. Compared to existing proofs for finite alphabets, our technique is simpler and self-contained. It also offers bounds on the asymptotic tail probability of the typicality event providing a scaling law for a large number of source encoders.

The multiple-input single-output (MISO) wiretap channel with K legitimate single-antenna receivers, one single-antenna eavesdropper in presence of delayed channel state information at the transmitter (CSIT) is considered. The transmitter is equipped with (K+1) antennas and has independent messages intended for each one of the K legitimate receivers. While for the case of a single receiver wiretap channel, i.e., K = 1, the optimal secure degrees of freedom (SDoF) with delayed CSIT was recently characterized in [1] and shown to be 2/3, the extension to the multi-receiver case (K > 1) is far from straightforward. We present new results and insights for the simplest non-trivial extension of this problem, i.e., for the case of K = 2 receiver MISO wiretap channel with delayed CSIT. The contribution of this paper is two fold: a) an asymptotic achievable scheme is presented for the case of two legitimate receivers which achieves a sum-SDoF of 36/37 and b) a novel converse proof is presented which shows that the sum-SDoF is upper bounded by 16/15.

The three-node multiterminal lossy source coding problem is investigated. We derive an inner bound to the general rate-distortion region of this problem which appears to be the natural extension of the seminal work by Kaspi [1] 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.

This work investigates the secrecy capacity region of the Wiretap Broadcast Channel (WBC) where an encoder communicates two private messages over a Broadcast Channel (BC) while keeping both messages secret from the eavesdropper. Our main result is the derivation of a novel outer bound and an inner bound on the secrecy capacity region of this setting. These results allow us to characterize the capacity region for three non-degraded classes of WBCs: the deterministic and the semi-deterministic WBC with a more noisy eavesdropper, and the WBC when users exhibit less noisiness order between them.

This work investigates the “2 by 1” two-user Compound Broadcast Channel. We investigate an evolved encoding scheme, based on the use of Multiple Description (MD) coding, where the source transmits both common and private descriptions to the many channel instances of the same user. We derive the resulting MD inner bound and evaluate it for the compound MISO BC resorting to a Dirty Paper Code (DPC). The suggested MD-DPC “strictly” outperforms Common Description (CD)-DPC and hence, palliates better the effect of channel uncertainty.

In this paper, we study the performance, in terms of the asymptotic error probability, of a user that communicates with a destination with the aid of a full-duplex in-band relay. We consider that the network is interference-limited, and interfering users are distributed as a Poisson point process. In this case, the asymptotic error probability is upper bounded by the outage probability (OP). We investigate the outage behavior for well-known cooperative schemes, namely, decode-and-forward (DF) and compress-and-forward (CF) considering fading and path loss. For DF, we determine the exact OP and develop upper bounds that are tight in typical operating conditions. Also, we find the correlation coefficient between source and relay signals that minimizes the OP when the density of interferers is small. For CF, the achievable rates are determined by the spatial correlation of the interferences, and a straightforward analysis is not possible. To handle this issue, we show that the rate with correlated noises is at most one bit worse than with uncorrelated noises and thus find an upper bound on the performance of CF. These results are useful to evaluate the performance and to optimize relaying schemes in the context of full-duplex wireless networks.

This paper investigates the problem of source-channel coding for secure transmission with arbitrarily correlated side informations at both receivers. This scenario consists of an encoder (referred to as Alice) that wishes to compress a source and send it through a noisy channel to a legitimate receiver (referred to as Bob). In this context, Alice must simultaneously satisfy the desired requirements on the distortion level at Bob and the equivocation rate at the eavesdropper (referred to as Eve). This setting can be seen as a generalization of the problems of secure source coding with (uncoded) side information at the decoders and the wiretap channel. A general outer bound on the rate-distortion-equivocation region, as well as an inner bound based on a pure digital scheme, is derived for arbitrary channels and side informations. In some special cases of interest, it is proved that this digital scheme is optimal and that separation holds. However, it is also shown through a simple counterexample with a binary source that a pure analog scheme can outperform the digital one while being optimal. According to these observations and assuming matched bandwidth, a novel hybrid digital/analog scheme that aims to gather the advantages of both digital and analog ones is then presented. In the quadratic Gaussian setup when side information is only present at the eavesdropper, this strategy is proved to be optimal. Furthermore, it outperforms both digital and analog schemes and cannot be achieved via time-sharing. Through an appropriate coding, the presence of any statistical difference among the side informations, the channel noises, and the distortion at Bob can be fully exploited in terms of secrecy.

This paper investigates the benefits of cooperation and proposes a relay activation strategy for a large wireless network with multiple transmitters. In this framework, some nodes cooperate with a nearby node that acts as a relay, using the decode-and-forward protocol, and others use direct transmission. The network is modeled as an independently marked Poisson point process, and the source nodes may choose their relays from the set of inactive nodes. Although cooperation can potentially lead to significant improvements in the performance of a communication pair, relaying causes additional interference in the network, increasing the average noise that other nodes see. We investigate how source nodes should balance cooperation versus interference to obtain reliable transmissions, and for this purpose, we study and optimize a relay activation strategy with respect to the outage probability. Surprisingly, in the high reliability regime, the optimized strategy consists on the activation of all the relays or none at all, depending on network parameters. We provide a simple closed-form expression that indicates when the relays should be active, and we introduce closed-form expressions that quantify the performance gains of this scheme with respect to a network that only uses direct transmission.

This paper investigates the potential gains of half-duplex unicast strategies in a large wireless network consisting of clusters in which a source node attempts to transmit a message with the aid of other inactive-potential relays- nodes within the cluster. The network is modeled as an independently marked Poisson point process and a slow-fading scenario is considered. A two-phase transmission protocol is studied and an achievable (upper) bound on the asymptotic error probability of any cluster in the network is derived in terms of the outage probability (OP). The proposed scheme takes advantage of the spatial distribution of the cooperating nodes to create a distributed virtual antenna array, thus improving the OP over direct transmission (DT) through cooperative diversity. Finally, we obtain a converse (lower) bound on the OP of any unicast strategy when restricting all admissible protocols to belong to the same-still quite general- class of half-duplex codes that includes the one studied.

Noisy Network Coding (NNC) was recently introduced, generalizing Compress-and-Forward (CF) to multiterminal networks. In this paper, we present Mixed Noisy Network Coding scheme as the generalization of NNC where part of the nodes are allowed to select Decode-and-Forward (DF) as their cooperative strategy while all nodes without exception transmit the compressed version of their observations. The compressed version of relays is exploited at each destination to decode the intended message. It is shown that Mixed NNC scheme performs potentially better than NNC. In particular, for AWGN networks it achieves a tighter ”constant gap” with respect to the cut-set bound, provided that DF relays are chosen properly.

We study the second-order coding rate of the multiple-input multiple-output (MIMO) Rayleigh block-fading channel via statistical bounds from information spectrum methods and random matrix theory. Based on an asymptotic analysis of the mutual information density which considers the simultaneous growth of the block length n and the number of transmit and receive antennas K and N, we derive closed-form upper and lower bounds on the optimal average error probability when the code rate is within O(1/√nK) of the asymptotic capacity. A Gaussian approximation is then used to establish an upper bound on the error probability for arbitrary code rates which is shown by simulations to be accurate for small N, K, and n.

This work investigates the general three-message compound broadcast channel (BC) where an encoder wishes to communicate a common and two private messages to two groups of users. We focus on the study of the largest achievable region when the encoder is constrained to use a single description per message that we refer to as “simplified random codes”. In this setting, we investigate the different roles that decoders can play at the destinations. Surprisingly enough, we show that simultaneous decoding of both the intended as well as the interference message at the destinations can strictly enlarge-in opposition with the standard BC- the rate region with respect to the worst-case (over all channels) of Marton's inner bound.

We define an “analog” index coding problem where a transmitter wishes to send a set of analog sources to be reconstructed with a desired distortion level at K receivers, each of which is characterized by a set of desired sources and by its own side information. The transmission channel is a multi-input single-output (MISO) broadcast channel with independent fading, perfect channel state information at the receiver and (strictly causal) feedback at the transmitter. An outer bound on the rate-distortion region is derived, revealing an interesting tradeoff between the communication rate (source samples per channel use) and the distortion exponential decay with snr in dB. We focus on the high-SNR and low-distortion regime, in which the proposed outer bound is shown to be tight for some cases of particular interest.

Consider the simultaneous relay channel (SRC) that consists of a set of relay channels where the source wishes to transmit common and private information to each of the destinations. This problem is recognized as being equivalent to that of sending common and private information to several destinations in presence of helper relays where each channel outcome becomes a branch of the broadcast relay channel (BRC). Cooperative schemes and capacity region for a set with two memoryless relay channels are investigated. The proposed coding schemes, based on decode-and-forward (DF) and compress-and-forward (CF), must be capable of transmitting information simultaneously to all destinations in such a set. Depending on the quality of source-to-relay and relay-to-destination channels, inner bounds on the capacity of the general BRC are derived. Three cases of particular interest are considered: 1) cooperation is based on DF strategy for both users, referred to as DF–DF region; 2) cooperation is based on CF strategy for both users, referred to as CF–CF region; and 3) cooperation is based on DF strategy for one destination and CF for the other, referred to as DF–CF region. These results can be seen as a generalization and hence unification of previous works. An outer bound on the capacity of the general BRC is also derived. Capacity results are obtained for the specific cases of semidegraded and degraded Gaussian SRCs. Rates are evaluated for Gaussian models where the source must guarantee a minimum amount of information to both users while additional information is sent to each of them.

The problem of secure multiterminal source coding with side information at the eavesdropper is investigated. This scenario consists of a main encoder (referred to as Alice) that wishes to compress a single source but simultaneously satisfying the desired requirements on the distortion level at a legitimate receiver (referred to as Bob) and the equivocation rate—average uncertainty—at an eavesdropper (referred to as Eve). It is further assumed the presence of a (public) rate-limited link between Alice and Bob. In this setting, Eve perfectly observes the information bits sent by Alice to Bob and has also access to a correlated source which can be used as side information. A second encoder (referred to as Charlie) helps Bob in estimating Alice's source by sending a compressed version of its own correlated observation via a (private) rate-limited link, which is only observed by Bob. For instance, the problem at hands can be seen as the unification between the Berger–Tung and the secure source coding setups. Inner and outer bounds on the so-called rate-distortion-equivocation region are derived. The inner region turns to be tight for two cases: 1) uncoded side information at Bob and 2) lossless reconstruction of both sources at Bob—secure distributed lossless compression. Application examples to secure lossy source coding of Gaussian and binary sources in the presence of Gaussian and binary/ternary (respectively) side informations are also considered. Optimal coding schemes are characterized for some cases of interest where the statistical differences between the side information at the decoders and the presence of a nonzero distortion at Bob can be fully exploited to guarantee secrecy.

The degrees of freedom (DoF) of the two-user Gaussian multiple-input and multiple-output (MIMO) broadcast channel with confidential messages is studied under the assumption that delayed channel state information (CSI) is available at the transmitter. We characterize the optimal secrecy DoF (SDoF) region and show that it can be achieved by a simple artificial noise alignment scheme. The proposed scheme sends the confidential messages superposed with the artificial noise over several time slots. Exploiting delayed CSI, the transmitter aligns the transmit signal in such a way that the useful message can be extracted at the intended receiver but is completely drowned by the artificial noise at the unintended receiver. The proposed scheme can be regarded as a nontrivial extension of Maddah-Ali Tse scheme and enables us to quantify the resource overhead, or equivalently the DoF loss, to be paid for the secure communications.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known noncausally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states noncausally transmits an individual message. We find explicit characterizations of the capacity region of this communication model in both discrete memoryless and memoryless Gaussian cases. In particular, the capacity region analysis demonstrates the utility of the knowledge of the states only strictly causally at the encoder that sends only the common message in general. More specifically, in the discrete memoryless setting, we show that such a knowledge is beneficial and increases the capacity region in general. In the Gaussian setting, we show that such a knowledge does not help, and the capacity is same as if the states were completely unknown at the encoder that sends only the common message. Furthermore, we also study the special case in which the two encoders transmit only the common message and show that the knowledge of the states only strictly causally at the encoder that sends only the common message is not beneficial in this case, in both discrete memoryless and memoryless Gaussian settings. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand–Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. By developing two optimal coding schemes that perform this state compression differently, we show that when used as parts of appropriately tuned encoding and decoding processes, both compression à-la noisy network coding by Limor the quantize-map-and-forward by Avestimeher, i.e., with no binning, and compression using Wyner–Ziv binning are optimal. The scheme that uses Wyner–Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely. Finally, by exploring the properties of our outer bound, we show that, although not required in general, the compression indices can in fact be decoded uniquely essentially without altering the capacity region, but at the expense of larger alphabets sizes for the auxiliary random variables.

We consider a three-terminal state-dependent relay channel with the channel state available noncausally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and noncognitive radios. We study the capacity of this communication model. One principal problem is caused by the relay's not knowing the channel state. For the discrete memoryless (DM) model, we establish two lower bounds and an upper bound on channel capacity. The first lower bound is obtained by a coding scheme in which the source describes the state of the channel to the relay and destination, which then exploit the gained description for a better communication of the source's information message. The coding scheme for the second lower bound remedies the relay's not knowing the states of the channel by first computing, at the source, the appropriate input that the relay would send had the relay known the states of the channel, and then transmitting this appropriate input to the relay. The relay simply guesses the sent input and sends it in the next block. The upper bound accounts for not knowing the state at the relay and destination. For the general Gaussian model, we derive lower bounds on the channel capacity by exploiting ideas in the spirit of those we use for the DM model; and we show that these bounds are optimal for small and large noise at the relay irrespective to the strength of the interference. Furthermore, we also consider a relay model with orthogonal channels from the source to the relay and from the source and relay to the destination in which the source input component that is heard by the relay does not depend on the channel states. We establish a better upper bound for both DM and Gaussian cases and we also characterize the capacity in a number of special cases.

This paper investigates the potential gain of cooperation in large wireless networks with multiple sources and relays, where the nodes form an homogeneous Poisson point process. The source nodes may choose their nearest neighbor from the set of inactive nodes as their relay. Although cooperation can potentially lead to significant improvements on the asymptotic error probability of a communication pair, relaying causes additional interference in the network, increasing the average noise. We address the basic question: how should source nodes optimally balance cooperation vs. interference to guarantee reliability in all communication pairs. Based on the decode-and-forward (DF) scheme at the relays, we derive closed-form approximations to the upper bounds on the error probability, averaging over all node positions. Surprisingly, in the small outage probability regime, there is an almost binary behavior that dictates - depending on network parameters - the activation or not of all relay nodes.

Consider a composite unicast relay network where the channel statistic is randomly drawn from a set of conditional distributions indexed by θ ϵ Θ, which is assumed to be unknown at the source, fully known at the destination and only partly known at the relays. Commonly, the coding strategy at each relay is fixed regardless of its channel measurement. A novel coding for unicast composite networks with multiple relays is introduced. This enables the relays to select dynamically-based on its channel measurement - the best coding scheme between compress-and-forward (CF) and decode-and-forward (DF). As a part of the main result, a generalization of Noisy Network Coding is shown for the case of unicast general networks where the relays are divided between those using DF and CF coding. Furthermore, the relays using DF scheme can exploit the help of those based on CF scheme via offset coding. It is demonstrated via numerical results that this novel coding, referred to as Selective Coding Strategy (SCS), outperforms conventional coding schemes.

This paper provides a novel central limit theorem (CLT) for the information density of the MIMO Rayleigh fading channel under white Gaussian inputs, when the data blocklength n and the number of transmit and receive antennas K and N, respectively, are large but of similar order of magnitude. This CLT is used to derive closed-form upper bounds on the error probability via an input-constrained version of Feinstein's lemma by Polyanskiy et al. and the second-order approximation of the coding rate. Numerical evaluations suggest that the normal approximation is tight for reasonably small values of n, K, N.

In this paper, the asymptotic iterative performance of block-Markov, sparse-graph codes over the binary erasure relay channel is investigated. Note that the full-duplex relay channel is a particular case of the considered model. We obtain two interesting results: a) the block-Markov structure does not improve the asymptotic performance of good erasure-correcting sparse-graph codes; b) under certain conditions, it does however improve the asymptotic performance of good erasure-detecting (i.e. bad erasure-correcting) sparse-graph codes.

This paper investigates the problem of source-channel coding for secure transmission of a Gaussian source over a Gaussian wiretap channel in presence of arbitrarily correlated side informations at both receivers. By means of an appropriate coding scheme (either hybrid digital/analog or pure digital), the optimal rate-distortion-equivocation region is characterized for most of the scenarios. These results provide the best achievable tradeoff between the requirement on the distortion level at the legitimate receiver and the equivocation rate at the eavesdropper.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We find explicit characterizations of the capacity region of this communication model. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand-Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. We show that both compression à-la noisy network coding, i.e., with no binning, and compression using Wyner-Ziv binning are optimal. The scheme that uses Wyner-Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely. Finally, by exploring the properties of our outer bound, we show that, although not required in general, the compression indices can in fact be decoded uniquely essentially without altering the capacity region, but at the expense of larger alphabets sizes for the auxiliary random variables.

This paper investigates composite multiterminal networks which consist of a set of multiterminal channels indexed or parametrized by a vector of channel parameters θ. The channel in operation is drawn from the sample set with probability Pθ. Instead of finding the maximum achievable rate subject to a -asymptotically- small error probability (EP), we look at the behavior of the error probability for a fixed coding rate. The asymptotic spectrum of error probability (ASEP) is then introduced as a novel and more general performance measure for composite networks. Indeed, the ASEP is defined as the smallest probability that the EP exceeds a desirable error ε for a coding rate r. It is shown that the ASEP is directly related to the ε-capacity of the network and assuming memoryless channels the ASEP can be bounded by a new region referred to as the full error region. Moreover, every code with a rate belonging to this region yields asymptotic EP equal to one.

Consider the communication of a single user aided by a nearby relay involved in a large and dense wireless network where the nodes form an homogeneous Poisson point process. We assume that the network is working in the interference-limited regime. In this case the asymptotic error probability is bounded from above by the outage probability experienced by the user. We investigate the outage behavior for the well-known cooperative schemes, namely, decode-and-forward (DF) and compress-and-forward (CF). In this setting, the outage events are induced by both fading and the spatial proximity of neighbor nodes who generate the strongest interference and hence the worst communication case. Upper and lower bounds on the asymptotic error probability which are tight in some cases are derived. It is shown that there exists a clear trade-off between the network density and the benefits of user cooperation. These results are useful to evaluate performance and to optimize relaying schemes in the context of large wireless networks.

Consider the composite relay channel consisting of a set of relay channels associated to a probability measure. The current channel is a draw from its probability and in some cases arbitrary small error probability cannot be guaranteed for all channels in the set. In this paper, instead of finding the maximum achievable rate subject to a small error probability (EP) for all the channels in the set, we look at the asymptotic behavior of EP for a given rate. The notion of achievable EP is introduced as a novel performance measure for wireless relay channels. We can intuitively define it as the smallest EP that can be asymptotically achieved for a given rate. The behavior of EP is directly related to the ϵ-capacity of each channel in the set. It is shown that the behavior of EP is upper and lower bounded by the outage probability of a region which is referred to as the full error region. Then every code with a rate belonging to this region yields EP equal to one. Finally, new coding for oblivious cooperation simultaneously exploiting both Decode-and-Forward (DF) and Compress-and-Forward (CF) strategies is investigated. The Gaussian relay channel with slow fading is also discussed.

The asymptotic iterative performance of the block-Markov encoding scheme, defined over bilayer LDPC codes, is analyzed. This analysis is carried out for both half-duplex and full-duplex regimes. For the sake of clarity and simplicity, a transmission over the binary erasure relay channel is assumed. To analyze the iterative performance of the coding scheme, the asymptotic threshold boundary γ (∈1, ∈2) is used as a performance measure. It is derived for two sparse-graph ensembles: Block-Markov Bilayer-Expurgated and -Lengthened LDPC ensembles.

The problem of secure lossy source-channel wiretapping with arbitrarily correlated side informations at both receivers is investigated. This scenario consists of an encoder (referred to as Alice) that wishes to compress a source and send it through a noisy channel to a legitimate receiver (referred to as Bob). In this context, Alice must simultaneously satisfy the desired requirements on the distortion level at Bob, and the equivocation rate at the eavesdropper (referred to as Eve). This setting can be seen as a generalization of the conventional problems of secure source coding with side information at the decoders, and the wiretap channel. Inner and outer bounds on the rate-distortion-equivocation region for the case of arbitrary channels and side informations are derived. In some special cases of interest, it is shown that separation holds. By means of an appropriate coding, the presence of any statistical difference among the side informations, the channel noises, and the distortion at Bob can be fully exploited in terms of secrecy.

The secrecy degrees of freedom (SDoF) of the Gaussian multiple-input and single-output (MISO) wiretap channel is studied under the assumption that delayed channel state information (CSI) is available at the transmitter and each receiver knows its own instantaneous channel. Such scenario is of practical interest since the legitimate receiver may send its channel states to the transmitter which is overheard by the eavesdropper. We first show that a strictly positive SDoF can be guaranteed whenever the transmitter has delayed CSI (either on the legitimate channel or/and the eavesdropper channel). In particular, in the case with delayed CSI on both channels, it is shown that the optimal SDoF is 2=3. We then generalize the result to the two-user Gaussian MISO broadcast channel with confidential messages and characterize the SDoF region when the transmitter has delayed CSI of both receivers. Interestingly, the artificial noise schemes are shown to provide the optimal SDoF region by masking the confidential message to the unintended receiver while aligning the interference at each receiver.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We study the capacity region of this communication model. In the discrete memoryless case, we establish inner and outer bounds on the capacity region. Although the encoder that sends both messages knows the states fully, we show that the strictly causal knowledge of these states at the other encoder can be beneficial for this encoder, and in general enlarges the capacity region. Furthermore, we find an explicit characterization of the capacity in the case in which the two encoders transmit only the common message. In the Gaussian case, we characterize the capacity region for the model with individual message as well. Our converse proof in this case shows that, for this model, strictly causal knowledge of the state at one of the encoders does not increase capacity if the other is informed non-causally, a result which sheds more light on the utility of conveying a compressed version of the state to the decoder in recent results by Lapidoth and Steinberg on a multiacess model with only strictly causal state at both encoders and independent messages.

Recent results on source-channel coding for secure transmission show that separation holds in several cases under some less-noisy conditions. However, it has also been proved through a simple counterexample that pure analog schemes can be optimal and hence outperform digital ones. According to these observations and assuming matched-bandwidth, we present a novel hybrid digital/analog scheme that aims to gather the advantages of both digital and analog ones. In the quadratic Gaussian setup when side information is only present at the eavesdropper, this strategy is proved to be optimal. Furthermore, it outperforms both digital and analog schemes and cannot be achieved via time-sharing. An application example to binary symmetric sources with side information is also investigated.

We consider a practical scenario of the Gaussian multiantenna wiretap channel where a transmitter with no channel state information wishes to send a confidential message to its legitimate receiver in the presence of an eavesdropper. It has been known that the secrecy capacity of such a channel does not scale with signal-to-noise ratio under general conditions. Taking into account the different temporal fading structures at the legitimate receiver and the eavesdropper, we characterize lower and upper bounds on the secrecy degrees of freedom (s.d.o.f.) of the channel at hand. Our results show that a positive s.d.o.f. can be ensured whenever two receivers experience the asynchronous variation. Remarkably, simple linear precoding schemes provide the optimal s.d.o.f. in most cases of interest by aligning either the confidential signal at the eavesdropper or the artificial noise at the legitimate receiver.

Consider the broadcast relay channel (BRC) which consists of a source sending information over a two user broadcast channel in presence of two relay nodes that help the transmission to the destinations. Clearly, this network with five nodes involves all the problems encountered in relay and broadcast channels. New inner bounds on the capacity region of this class of channels are derived. These results can be seen as a generalization and hence unification of previous work in this topic. Our bounds are based on the idea of recombination of message bits and various effective coding strategies for relay and broadcast channels. Capacity result is obtained for the semi-degraded BRC-CR, where one relay channel is degraded while the other one is reversely degraded. An inner and upper bound is also presented for the degraded BRC with common relay (BRC-CR), where both the relay and broadcast channel are degraded which is the capacity for the Gaussian case. Application of these results arise in the context of opportunistic cooperation of cellular networks.

We consider the multi-antenna wiretap channel in which the transmitter wishes to send a confidential message to its receiver while keeping it secret to the eavesdropper. It has been known that the secrecy capacity of such a channel does not increase with signal-to-noise ratio when the transmitter has no channel state information (CSI) under mild conditions. Motivated by Jafar's robust interference alignment technique, we study the so-called staggered multi-antenna block-fading wiretap channel where the legitimate receiver and the eavesdropper have different temporal correlation structures. Assuming no CSI at transmitter, we characterize lower and upper bounds on the secrecy degrees of freedom (s.d.o.f.) of the channel at hand. Our results show that a positive s.d.o.f. can be ensured whenever two receivers experience different fading variation. Remarkably, very simple linear precoding schemes provide the optimal s.d.o.f. in some cases of interest.

This paper investigates the capacity of compound state-dependent channels with non-causal state information available at only the transmitter. A new lower bound on the capacity of this class of channels is derived. This bound is shown to be tight for the special case of compound channels with stochastic degraded components, yielding the full characterization of the capacity. Specific results are derived for the compound Gaussian Dirty-Paper (GDP) channel. This model consists of an additive white Gaussian noise (AWGN) channel corrupted by an additive Gaussian interfering signal, known at the transmitter only, where the input and the state signals are affected by fading coefficients whose realizations are unknown at the transmitter. Our bounds are shown to be tight for specific cases. Applications of these results arise in a variety of wireless scenarios as multicast channels, cognitive radio and problems with interference cancellation.

We consider a three-terminal state-dependent relay channel with the channel state available non-causally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and non-cognitive radios. We study the capacity of this communication model. One principal problem in this setup is caused by the relay's not knowing the channel state. In the discrete memoryless (DM) case, we establish lower bounds on channel capacity. For the Gaussian case, we derive lower and upper bounds on the channel capacity. The upper bound is strictly better than the cut-set upper bound. We show that one of the developed lower bounds comes close to the upper bound, asymptotically, for certain ranges of rates.

The simultaneous relay channel is investigated where the source is unaware of the channel statistic controlling the communication but knows that this statistic is one of two possible discrete memoryless relay channels. We aim to derive coding schemes capable of transmitting information, regardless of which of these relays is present. First, this problem is recognized as being equivalent to that of sending common and private information to two destinations in presence of two helper relays. In this scenario, each possible relay links becomes a branch of the so-called broadcast relay channel. An inner bound on the capacity region of this channel is derived. Applications of these results arise when the source node is uncertain of the noise levels or the network topology (e.g. due to user mobility the positions of the relay and the destination nodes are unknown). Specific rates are computed for an AWGN relay channel, where the relay node may be absent but the source node is unaware of this.

The problem of sending information over compound state-dependent channels with non-causal state information available at only the transmitter is investigated. We prove a coding theorem and its strong converse establishing the capacity of this scenario for the case of discrete memoryless channels. Specific results are derived for additive white Gaussian noise channels corrupted by an additive Gaussian interference which is available at the transmitter only. We focus on the case where such interference may be absent on the channel, but the transmitter is unaware of this. Applications of the compound channels with non-causal state information arise in the context of multicast and cognitive radio channels, broadcast channels with imperfect channel knowledge and robust dirty-paper coding.

The optimal decoder achieving the outage capacity under imperfect channel estimation is investigated. First, by searching into the family of nearest neighbor decoders, which can be easily implemented on most practical coded modulation systems, we derive a decoding metric that minimizes the average of the transmission error probability over all channel estimation errors. Next, we specialize our general expression to obtain the corresponding decoding metric for fading MIMO channels. According to the notion of Estimation-induced outage (EIO) capacity introduced in our previous work and assuming a block Rayleigh-fading channel, we characterize the maximal achievable information rates using Gaussian codebooks associated to the proposed decoder. These achievable rates are compared to the rates achieved by the classical mismatched maximum likelihood (ML) decoder and the ultimate limits given by the EIO capacity. Numerical results show that the derived metric provides significant gains, in terms of achievable EIO rates and bit error rate (BER), in a bit interleaved coded modulation (BICM) framework, without introducing any additional decoding complexity. However, the achievable rates of such metric are still far from the EIO capacity.

Communication systems are usually designed by assuming perfect channel state information (CSI). However, in many practical scenarios, only a noisy estimate of the channel is available, which may strongly differ from the true channel. This imperfect CSI scenario is addressed by introducing the notion ofestimation-induced outage (EIO). We derive a single-letter characterization of the maximal EIO rate and prove an associated coding theorem and its strong converse for discrete memoryless channels (DMCs). The transmitter and the receiver rely on the channel estimate and the statistics of the estimate to construct codes that guarantee reliable communication with a certain outage probability. This ensures that in the non-outage case the transmission meets the target rate with small error probability, irrespective of the quality of the channel estimate. Applications of the EIO capacity to a single-antenna (nonergodic) Ricean fading channel are considered. The EIO capacity for this case is compared to the EIO rates of a communication system in which the receiver decodes by using a mismatched maximum-likelihood (ML) decoder. The effects of rate-limited feedback to provide the transmitter with quantized CSI are also investigated.

The design of efficient rateless coding schemes for multicast applications in wireless environments is investigated. First, the rateless paradigm for non-ergodic channels is introduced by making use of the dynamic-decoding nature of rateless codes that allows them to adapt opportunistically the code rate to the channel realization (assumed unknown at the transmitter). The information theoretical limits of such codes can be interpreted in terms of the notion of outage capacity. Then, we consider a quasi-static Rayleigh-fading channel with perfect and imperfect channel state information (CSI) at the receiver. We show that the optimal consistent measure of information for decoding with imperfect CSI, is given by the log-likelihood ratio (LLR) of the received bits via a composite (more noisy) channel. The optimization of Raptor codes, which depends on the delay requirements of decoding, is obtained by using Information content evolution under Gaussian approximation. Simulation results show that optimized Raptor codes can operate very close to the theoretical limits on a wide range of delay requirements.

This paper investigates the effect of channel estimation errors in presence of spatial correlation for fading MIMO multiple access channels (MACs). Specifically, the capacity is derived under the notion of reliable communication based on the average of the error probability over all channel estimation errors. Although not necessarily optimality in presence of channel estimation errors, we restrict the channel inputs to be Gaussians, allowing a closed-form expression for the mutual information, which leads to an inner bound of the capacity region. For different types of transmitter information (e.g. instantaneous and covariance information), we study optimal transmission schemes that permit to maximize the sum-rate. Numerical results show that the performance of covariance feedback is quite sensitive to channel accuracy while the gap between the open-loop and the closed-loop scenario increases with the channel uncertainty. Simulations also assess the performance degradation of transmit/receive correlation and reveal that their impact behaves independently of the estimation errors.

Consider a base station transmitting information over a downlink wireless communication channel, where the mobiles (the receivers) only dispose of a noisy estimate of the channel parameters, and these estimates are not available at the base station (the transmitter). In this paper, we examine the effects of imperfect channel estimation at the receivers and no channel knowledge at the transmitter on the capacity of the multiuser fading MIMO broadcast channel. We derive the optimal dirty-paper coding (DPC) scheme and its corresponding achievable rates with the assumption of Gaussian inputs. Our results, for uncorrelated Rayleigh fading, are particularly useful for a system designer to assess the amount of training data and the channel characteristics (e.g. SNR, fading process, number of antennas) to achieve target rates. We provide numerical results for a two-users MIMO broadcast channel with maximum-likelihood (ML) channel estimation. These illustrate a practical trade-off between the amount of training and its impact to the multiuser interference cancellation performance. In particular, we observe the surprising result that a broadcast channel with a single transmitter and receiver antenna, and imperfect channel estimation at the receivers, does not need the knowledge of estimates at the transmitter to achieve large rates.

In this paper, we examine the effects of imperfect channel estimation at the receiver and no channel knowledge at the transmitter on the capacity of the fading Costa's channel with channel state information non-causally known at the transmitter. We derive the optimal dirty-paper coding (DPC) scheme and its corresponding achievable rates with the assumption of Gaussian inputs. Our results, for uncorrelated Rayleigh fading, provide intuitive insights on the impact of the channel estimate and the channel characteristics (e.g. SNR, fading process, channel training) on the achievable rates. These are useful in practical scenarios of multiuser wireless communications (e.g. Broadcast Channels) and information embedding applications (e.g. robust watermarking). We also studied optimal training design adapted to each application. We provide numerical results for a single-user fading Costa's channel with maximum-likehood (ML) channel estimation. These illustrate an interesting practical trade-off between the amount of training and its impact to the interference cancellation performance using DPC scheme.

The optimal decoder achieving the outage capacity under imperfect channel estimation is investigated. First, by searching into the family of nearest neighbor decoders, which can be easily implemented on most practical coded modulation systems, we derive a decoding metric that minimizes the average of the transmission error probability over all channel estimation errors. This metric, for arbitrary memoryless channels, achieves the capacity of a composite (more noisy) channel. Next, according to the notion of estimation-induced outage capacity (EIO capacity) introduced in our previous work, we characterize maximal achievable information rates associated to the proposed decoder. The performance of the proposed decoding metric over uncorrelated Rayleigh fading MIMO channels is compared to both the classical mismatched maximum-likelihood (ML) decoder and the theoretical limits given by the EIO capacity (i.e. the best decoder in presence of channel estimation errors). Numerical results show that the derived metric provides significant gains, in terms of achievable information rates and bit error rate (BER), in a bit interleaved coded modulation (BICM) framework, without introducing any additional decoding complexity.

Multiple user information embedding is concerned with embedding several messages into the same host signal. While emphasizing the tight relationship with conventional multiple user information theory, this paper presents several implementable "dirty paper coding" (DPC) based schemes for multiple user information embedding. These are obtained by exploring strong connections with the well-known Gaussian multiple access channel (MAC) with state information at the encoders. Two practical schemes are compared. The first -rather intuitive- consists in a straightforward superimposition of DPC schemes. The second consists in a joint design of these dirty paper coding schemes, based on the ideal DPC-based coding for the equivalent MAC channel. These results extend to the multiple user case the practical implementations (QIM and SCS) that have been originally conceived for one user. Then, we extend the results to a more general coding based on lattice (vector) codebooks, showing that the gap to full performances can be bridged up by using finite dimensional lattice codebooks, at the cost of an increased computational complexity. The improvements brought by a joint design are illustrated by bit error rates curves and achievable rates region

Multiple watermarking is concerned with embedding several messages into the same host signal, with different robustness and transparency requirements. This paper proposes two implementable scalar schemes for multiple user "dirty paper coding". The first - straightforward - approach consists of an independent superposition of two scalar dirty paper coding schemes. The second consists in the joint design of a scalar dirty paper coding. This joint approach is based on the ideal dirty paper coding scheme for broadcast channels with noncausal side information known to the transmitter. For this purpose, the "scalar Costa scheme" that has been originally conceived for one user is extended to two users. Performance evaluations, including bit error rates and capacity region curves are provided for both methods, illustrating the improvements brought by a joint design.