Self-supervised graph representation learning (GRL) typically generates paired graph augmentations from each graph to infer similar representations for augmentations of the same graph, but distinguishable representations for different graphs. While effective augmentation requires both semantics-preservation and data-perturbation, most existing GRL methods focus solely on data-perturbation, leading to suboptimal solutions. To fill the gap, in this paper, we propose a novel method, Explanation-Preserving Augmentation (EPA), which leverages graph explanation for semantics-preservation. EPA first uses a small number of labels to train a graph explainer, which infers the subgraphs that explain the graph’s label. Then these explanations are used for generating semantics-preserving augmentations for boosting self-supervised GRL. Thus, the entire process, namely EPA-GRL, is semi-supervised. We demonstrate theoretically, using an analytical example, and through extensive experiments on a variety of benchmark datasets, that EPA-GRL outperforms the state-of-the-art (SOTA) GRL methods that use semantics-agnostic augmentations.

Graph Neural Networks (GNNs) are essential for processing graph-structured data and have wide applications in critical domains. The increasing use of GNNs in high-stakes scenarios requires robust explainability to ensure trust and transparency in decision-making. A common approach to explaining GNNs is to identify subgraphs, a.k.a. explanations, that significantly influence model predictions. However, this task is challenging due to the distribution shifts from the original training graphs to the explanation subgraphs, a factor that is largely overlooked in the existing research. These shifts arise because GNNs are trained on original graphs, while explanation subgraphs often differ in properties such as the number of nodes or structural patterns. As a result, GNNs may struggle to generalize to explanation subgraphs with a different distribution from its training data. In this paper, we systematically investigate the Out-Of-Distribution (OOD) problem through theoretical analysis and empirical studies. To address this challenge, we first develop a theoretical framework that formalizes the notion of explanation subgraphs through sufficiency and minimality criteria, ensuring both prediction preservation and structural compactness. Our analysis reveals a fundamental distributional disparity between explanation subgraphs and original graphs, leading to a novel concept of proxy graphs proposed in this work. Proxy graphs maintain the essential explanatory information while conforming to the original data distribution through a combination of parametric and non-parametric optimization approaches. Empirical evaluations on diverse datasets show that our method improves the quality and reliability of GNN explanations, advancing the field of GNN explainability.

Recent research has developed a number of eXplainable AI (XAI) techniques, such as gradient-based approaches, input perturbation-base methods, and black-box explanation methods. While these XAI techniques can extract meaningful insights from deep learning models, how to properly evaluate them remains an open problem. The most widely used approach is to perturb or even remove what the XAI method considers to be the most important features in an input and observe the changes in the output prediction. This approach, although straightforward, suffers the Out-of-Distribution (OOD) problem as the perturbed samples may no longer follow the original data distribution. A recent method RemOve And Retrain (ROAR) solves the OOD issue by retraining the model with perturbed samples guided by explanations. However, using the model retrained based on XAI methods to evaluate these explainers may cause information leakage and thus lead to unfair comparisons. We propose Fine-tuned Fidelity (F-Fidelity), a robust evaluation framework for XAI, which utilizes i) an explanation-agnostic fine-tuning strategy, thus mitigating the information leakage issue, and ii) a random masking operation that ensures that the removal step does not generate an OOD input. We also design controlled experiments with state-of-the-art (SOTA) explainers and their degraded version to verify the correctness of our framework. We conduct experiments on multiple data modalities, such as images, time series, and natural language. The results demonstrate that F-Fidelity significantly improves upon prior evaluation metrics in recovering the ground-truth ranking of the explainers. Furthermore, we show both theoretically and empirically that, given a faithful explainer, F-Fidelity metric can be used to compute the sparsity of influential input components, i.e., to extract the true explanation size.

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ($X^{d}, Y^{d}$) generated based on the joint distribution$P_{X, Y}$. The agents wish to produce a pair of discrete random variables$\left(U_{d}, V_{d}\right)$with joint distribution$P_{U_{d}, V_{d}}$, such that$P_{U_{d}, V_{d}}$converges in total variation distance to a target distribution$Q_{U, V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to$\left(X^{d}, Y^{d}\right)$, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with$\left(X^{d}, Y^{d}\right)$to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit$Z$, in addition to ($X^{d}, Y^{d}$). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences$X^{d}$and$Y^{d}$drawn according to a joint distribution$P_{X^{d}Y^{d}}$. The agents aim to generate outputs$U=f_{d}(X^{d})$and$V=g_{d}(Y^{d})$with a joint distribution sufficiently close in total variation to a target distribution$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is$O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is$\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions$(f_{d}(X^{d}),g_{d}(Y^{d}))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.

Graph Neural Networks (GNNs) have received increasing attention due to their ability to learn from graph-structured data. To open the black-box of these deep learning models, post-hoc instance-level explanation methods have been proposed to understand GNN predictions. These methods seek to discover substructures that explain the prediction behavior of a trained GNN. In this paper, we show analytically that for a large class of explanation tasks, conventional approaches, which are based on the principle of graph information bottleneck (GIB), admit trivial solutions that do not align with the notion of explainability. Instead, we argue that a modified GIB principle may be used to avoid the aforementioned trivial solutions. We further introduce a novel factorized explanation model with theoretical performance guarantees. The modified GIB is used to analyze the structural properties of the proposed factorized explainer. We conduct extensive experiments on both synthetic and real-world datasets to validate the effectiveness of our proposed factorized explainer.

Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. GNNs have emerged as pivotal architectures in analyzing graph-structured data, and their expansive application in sensitive domains requires a comprehensive understanding of their decision-making processes --- necessitating a framework for GNN explainability. An explanation function for GNNs takes a pre-trained GNN along with a graph as input, to produce a `sufficient statistic' subgraph with respect to the graph label. A main challenge in studying GNN explainability is to provide fidelity measures that evaluate the performance of these explanation functions. This paper studies this foundational challenge, spotlighting the inherent limitations of prevailing fidelity metrics, including $Fid_+$, $Fid_-$, and $Fid_\Delta$. Specifically, a formal, information-theoretic definition of explainability is introduced and it is shown that existing metrics often fail to align with this definition across various statistical scenarios. The reason is due to potential distribution shifts when subgraphs are removed in computing these fidelity measures. Subsequently, a robust class of fidelity measures are introduced, and it is shown analytically that they are resilient to distribution shift issues and are applicable in a wide range of scenarios. Extensive empirical analysis on both synthetic and real datasets are provided to illustrate that the proposed metrics are more coherent with gold standard metrics.

Explaining deep learning models operating on time series data is crucial in various applications of interest which require interpretable and transparent insights from time series signals. In this work, we investigate this problem from an information theoretic perspective and show that most existing measures of explainability may suffer from trivial solutions and distributional shift issues. To address these issues, we introduce a simple yet practical objective function for time series explainable learning. The design of the objective function builds upon the principle of information bottleneck (IB), and modifies the IB objective function to avoid trivial solutions and distributional shift issues. We further present TimeX++, a novel explanation framework that leverages a parametric network to produce explanation-embedded instances that are both in-distributed and label-preserving. We evaluate TimeX++ on both synthetic and real-world datasets comparing its performance against leading baselines, and validate its practical efficacy through case studies in a real-world environmental application. Quantitative and qualitative evaluations show that TimeX++ outperforms baselines across all datasets, demonstrating a substantial improvement in explanation quality for time series data. The source code is available at https://github.com/zichuan-liu/TimeXplusplus.

In task-based quantization, a multivariate analog signal is transformed into a digital signal using a limited number of low-resolution analog-to-digital converters (ADCs). This process aims to minimize a fidelity criterion, which is assessed against an unobserved task variable that is correlated with the analog signal. The scenario models various applications of interest such as channel estimation, medical imaging applications, and object localization. This work explores the integration of analog processing components-such as analog delay elements, polynomial operators, and envelope detectors-prior to ADC quantization. Specifically, four scenarios, involving different collections of analog processing operators are considered: (i) arbitrary polynomial operators with analog delay elements, (ii) limited-degree polynomial operators, excluding delay elements, (iii) sequences of envelope detectors, and (iv) a combination of analog delay elements and linear combiners. For each scenario, the minimum achievable distortion is quantified through derivation of computable expressions in various statistical settings. It is shown that analog processing can significantly reduce the distortion in task reconstruction. Numerical simulations in a Gaussian example are provided to give further insights into the aforementioned analog processing gains.

This work considers an information-theoretic characterization of the set of achievable rates, costs, and distortions in a broad class of distributed communication and function computation scenarios with general continuous-valued sources and channels. A framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order to evaluate the resulting achievable regions, convergence results for information measures are provided under the proposed discretization process. Prior works have considered such convergence results for mutual information quantities written in terms of univariate functions of random variables, and sums of independent random variables. These convergence results have been used to derive achievable regions in point-to-point communication scenarios and specific multiterminal scenarios with continuous alphabets. However, the best-known achievability results for distributed communication and function computation scenarios, which are based on structured coding strategies, involve mutual information quantities written in terms of bivariate functions of random variables, e.g., sum of two (not necessarily independent) random variables. A main contribution of this work is to show the convergence of mutual information quantities written in terms of sums of quantized random variables. This is an essential step in evaluating the achievable regions in continuous distributed computation scenarios by generalizing the structured coding strategies which have been previously used to derive the best-known achievable regions in discrete networks. The framework is used to provide achievability results for the problems of function computation over multiple-access channels, distributed source coding, function reconstruction (two-help-one), and multiple-descriptions source coding. In each scenario, discrete structured coding strategies along with the aforementioned convergence results are used to derive inner bounds to set of achievable rates, costs, and distortions. Furthermore, structured coding strategies are considered for distributed function computation scenarios involving computation of non-additive functions. The techniques are used to study an example where the objective is to compute the product of channel inputs over a multiple access channel, and an inner bound to the achievable rate region is evaluated. It is shown that, in contrast to many well-studied scenarios in multiterminal information theory, Gaussian input distribution is outperformed by the uniform input distribution.

Dataset obfuscation refers to techniques in which random noise is added to the entries of a given dataset, prior to its public release, to protect against leakage of private information. In this work, dataset obfuscation under two objectives is considered: i) rank-preservation: to preserve the row ordering in the obfuscated dataset induced by a given rank function, and ii) anonymity: to protect user anonymity under fingerprinting attacks. The first objective, rank-preservation, is of interest in applications such as the design of search engines and recommendation systems, feature matching, and social network analysis. Fingerprinting attacks, considered in evaluating the anonymity objective, are privacy attacks where an attacker constructs a fingerprint of a victim based on its observed activities, such as online web activities, and compares this fingerprint with information extracted from a publicly released obfuscated dataset to identify the victim. By evaluating the performance limits of a class of obfuscation mechanisms over asymptotically large datasets, a fundamental trade-off is quantified between rank-preservation and user anonymity. Single-letter obfuscation mechanisms are considered, where each entry in the dataset is perturbed by independent noise, and their fundamental performance limits are characterized by leveraging large deviation techniques. The optimal obfuscating test-channel, optimizing the privacy-utility tradeoff, is characterized in the form of a convex optimization problem which can be solved efficiently. Numerical simulations of various scenarios are provided to verify the theoretical derivations.

Distributed estimation in the context of sensor networks is considered, where distributed agents are given a set of sensor measurements, and are tasked with estimating a target variable. A subset of sensors are assumed to be faulty. The objective is to minimize i) the mean squared estimation error at each node (accuracy objective), and ii) the mean squared distance between the estimates at each pair of nodes (consensus objective). It is shown that there is an inherent tradeoff between the former and latter objectives. Assuming a general stochastic model, the sensor fusion algorithm optimizing this tradeoff is characterized through a computable optimization problem, and a Cramér-Rao type lower bound for the achievable accuracy-consensus loss is obtained. Finding the optimal sensor fusion algorithm is computationally complex. To address this, a general class of low-complexity Brooks-Iyengar Algorithms are introduced, and their performance, in terms of accuracy and consensus objectives, is compared to that of optimal linear estimators through case study simulations of various scenarios.

The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

This work considers necessary conditions for privacy guarantees under active fingerprinting attacks in power-law bipartite networks. The scenario arises naturally in social network analysis, tracking user mobility in wireless networks, and forensics applications, among others. A stochastic growing network generation model — called the popularity-based model — is investigated, where the bipartite network is generated iteratively, and in each iteration vertices attract new edges based on their assigned popularity values. It is shown that using the appropriate choice of initial popularity values, the node degree distribution follows a power-law distribution with arbitrary parameter α > 2, i.e. fraction of nodes with degree d is proportional to d−α. An active fingerprinting deanonymization attack strategy called the augmented information threshold attack strategy (A-ITS) is proposed which uses the attacker’s knowledge of the node degree distribution along with the concept of information values for deanonymization. Sufficient conditions for the success of the A-ITS, based on network parameters, are derived. It is shown through simulations that the proposed attack significantly outperforms the state-of-the-art attack strategies.

Analog to Digital Converters (ADCs) are a major contributor to the energy consumption on the receiver side of millimeter-wave multiple-input multiple-output (MIMO) systems with large antenna arrays. Consequently, there has been significant interest in using low-resolution ADCs along with hybrid beamforming at MIMO receivers for energy efficiency. However, decreasing the ADC resolution results in performance loss — in terms of achievable rates — due to increased quantization error. In this work, we study the application of practically implementable nonlinear analog operations, prior to sampling and quantization at the ADCs, as a way to mitigate the afore-mentioned rate-loss. A receiver architecture consisting of linear analog combiners, implementable nonlinear analog operators, and one-bit threshold ADCs is designed. The fundamental information theoretic performance limits of the resulting communication system, in terms of achievable rates, are investigated under various assumptions on the set of implementable nonlinear analog functions. In order to justify the feasibility of the nonlinear operations in the proposed receiver architecture, an analog circuit is introduced, and circuit simulations exhibiting the generation of the desired nonlinear analog operations are provided.

The paper addresses the fundamental information theoretic limits — in terms of achievable rates and distortions — in a broad class of multiterminal communication scenarios with general continuous-valued sources and channels. A general framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order to evaluate fundamental performance limits under the proposed discretization process, convergence results for information measures are provided. The framework is used to study the distributed source coding in source coding, as well as the computation over multiple access channels in channel coding. In each case, a communication scheme is presented, the resulting achievable region is derived, and the region is evaluated for Gaussian sources and channels.

In-band full-duplex (FD) communication has emerged as one of the promising techniques to improve data rates in next generation wireless systems. Typical FD scenarios considered in the literature assume FD base stations (BSs) and half-duplex (HD) users activated either in uplink (UL) or downlink (DL), where inter-user interference (IUI) is treated as noise at the DL user. This paper considers more general FD scenarios where an arbitrary fraction of the users are capable of FD and/or they can perform successive interference cancellation (SIC) to mitigate IUI. Consequently, one user can be activated in either UL or DL (HD-UL and HD-DL modes), or simultaneously in both directions requiring self-interference mitigation (SIM) at that user (FD-SIM mode). Furthermore, two users can be scheduled, one in UL and the other in DL (both operating in HD), where the DL user can treat IUI as noise (FD-IN mode) or perform SIC to mitigate IUI (FD-SIC mode). This paper studies opportunistic mode selection and user scheduling under long-term and short-term temporal fairness in single-carrier and multi-carrier (OFDM) FD systems, with the goal of maximizing system utility (e.g. sum-rate). First, the feasible region of temporal demands is characterized for both long-term and short-term fairness. Subsequently, optimal temporal fair schedulers as well as practical low-complexity online algorithms are devised. Simulation results demonstrate that using SIC to mitigate IUI as well as having FD capability at users can improve FD throughput gains significantly especially, when user distribution is concentrated around a few hotspots.

This work considers active deanonymization of bipartite networks. The scenario arises naturally in evaluating privacy in various applications such as social networks, mobility networks, and medical databases. For instance, in active deanonymization of social networks, an anonymous victim is targeted by an attacker (e.g. the victim visits the attacker’s website), and the attacker queries her group memberships (e.g. by querying the browser history) to deanonymize her. In this work, the fundamental limits of privacy, in terms of the minimum number of queries necessary for deanonymization, is investigated. A stochastic model is considered, where 1) the bipartite network of group memberships is generated randomly; 2) the attacker has partial prior knowledge of the group memberships; and 3) it receives noisy responses to its real-time queries. The bipartite network is generated based on linear and sublinear preferential attachment, and the stochastic block model. The victim’s identity is chosen randomly based on a distribution modeling the users’ risk of being the victim (e.g. probability of visiting the website). An attack algorithm is proposed which builds upon techniques from communication with feedback, and its performance, in terms of expected number of queries, is analyzed. Simulation results are provided to verify the theoretical derivations.

High resolution analog to digital converters (ADCs) are conventionally used at the receiver terminals to store an accurate digital representation of the received signal, thereby allowing for reliable decoding of transmitted messages. However, in a wide range of applications, such as communication over millimeter wave and massive multiple-input multiple-output (MIMO) systems, the use of high resolution ADCs is not feasible due to power budget limitations. In the conventional fully digital receiver design, where each receiver antenna is connected to a distinct ADC, reducing the ADC resolution leads to performance loss in terms of achievable rates. One proposed method to mitigate the rate-loss is to use analog linear combiners leading to design of hybrid receivers. Here, the hybrid framework is augmented by the addition of delay elements to allow for temporal analog processing. Two new classes of receivers consisting of delay elements, analog linear combiners, and one-bit ADCs are proposed. The fundamental limits of communication in single and multi-user (uplink and downlink) MIMO systems employing the proposed receivers are investigated. In the high signal to noise ratio regime, it is shown that the proposed receivers achieve the maximum achievable rates among all receivers with the same number of one-bit ADCs.

In this paper, matching pairs of stocahstically generated graphs in the presence of generalized seed side-information is considered. The graph matching problem emerges naturally in various applications such as social network de-anonymization, image processing, DNA sequencing, and natural language processing. A pair of randomly generated labeled Erdös-Rényi graphs with pairwise correlated edges are considered. It is assumed that the matching strategy has access to the labeling of the vertices in the first graph, as well as a collection of shortlists — called ambiguity sets — of possible labels for the vertices of the second graph. The objective is to leverage the correlation among the edges of the graphs along with the side-information provided in the form of ambiguity sets to recover the labels of the vertices in the second graph. This scenario can be viewed as a generalization of the seeded graph matching problem, where the ambiguity sets take a specific form such that the exact labels for a subset of vertices in the second graph are known prior to matching. A matching strategy is proposed which operates by evaluating the joint typicality of the adjacency matrices of the graphs. Sufficient conditions on the edge statistics as well as ambiguity set statistics are derived under which the proposed matching strategy successfully recovers the labels of the vertices in the second graph. Additionally, Fano-type arguments are used to derive necessary conditions for successful seeded graph matching.

In this work, lossy distributed compression of a pair of correlated sources is considered. Conventionally, Shannon's random coding arguments - using randomly generated unstructured codebooks whose blocklength is taken to be asymptotically large - are used to derive achievability results. However, in some multi-terminal communications scenarios, using random codes with constant finite blocklength in certain coding architectures leads to improved achievable regions compared to the conventional approach. In other words, in some network communication scenarios, there is a finite optimal value in the blocklength of the randomly generated code used for distributed processing of information sources. Motivated by this, a coding scheme is proposed which consists of two codebook layers: i) the primary codebook which has constant finite blocklength, and ii) the secondary codebook whose blocklength is taken to be asymptotically large. The achievable performance is analyzed in two steps. In the first step, a characterization of an inner bound to the achievable region is derived in terms information measures which are functions of multi-letter probability distributions. In the next step, a computable single-letter inner-bound to the achievable region is extracted. It is shown through an example that the resulting rate-distortion region is strictly larger than the Berger-Tung achievable region.

Use of low resolution analog to digital converters (ADCs) is an effective way to reduce the high power consumption of millimeter wave (mmWave) receivers. In this paper, a receiver with low resolution ADCs based on adaptive thresholds is considered in downlink mmWave communications in which the channel state information is not known a-priori and acquired through channel estimation. A performance comparison of low-complexity algorithms for power and ADC allocation among transmit and receive terminals, respectively, is provided. Through simulation of practical mmWave cellular networks, it is shown that the use of low resolution ADCs does not significantly degrade the system throughput (as compared to a conventional fully digital high resolution receiver) when using the adaptive threshold receiver in conjunction with simple power and ADC allocation strategies.

In this paper, matching of correlated high-dimensional databases is investigated. A stochastic database model is considered where the correlation among the database entries is governed by an arbitrary joint distribution. Concentration of measure theorems such as typicality and laws of large numbers are used to develop a database matching scheme and derive necessary conditions for successful matching. Furthermore, it is shown that these conditions are tight through a converse result which characterizes a set of distributions on the database entries for which reliable matching is not possible. The necessary and sufficient conditions for reliable matching are evaluated in the cases when the database entries are independent and identically distributed as well as under Markovian database models.

Analog-to-digital converters (ADCs) are a major contributor to the power consumption of multiple-input multiple-output (MIMO) communication systems with large number of antennas. Use of low resolution ADCs has been proposed as a means to decrease power consumption in MIMO receivers. However, reducing the ADC resolution leads to performance loss in terms of achievable transmission rates. In order to mitigate the rate-loss, the receiver can perform analog processing of the received signals before quantization. Prior works consider one-shot analog processing where at each channel-use, analog linear combinations of the received signals are fed to a set of one-bit threshold ADCs. In this paper, a receiver architecture is proposed which uses a sequence of delay elements to allow for blockwise linear combining of the received analog signals. In the high signal to noise ratio regime, it is shown that the proposed architecture achieves the maximum achievable transmission rate given a fixed number of one-bit ADCs. Furthermore, a tradeoff between transmission rate and the number of delay elements is identified which quantifies the increase in maximum achievable rate as the number of delay elements is increased.

The fundamental limits of communication over multiple-input multiple-output (MIMO) networks are considered when a limited number of one-bit analog to digital converters (ADC) are used at the receiver terminals. Prior works have mainly focused on point-to-point communications, where receiver architectures consisting of a concatenation of an analog processing module, a limited number of one-bit ADCs with non-adaptive thresholds, and a digital processing module are considered. In this work, a new receiver architecture is proposed which utilizes adaptive threshold one-bit ADCs - where the ADC thresholds at each channel-use are dependent on the channel outputs in the previous channel-uses - to mitigate the quantization rate-loss. Coding schemes are proposed for communication over the point-to-point and broadcast channels, and achievable rate regions are derived. In the high SNR regime, it is shown that using the proposed architectures and coding schemes leads to the largest achievable rate regions among all receiver architectures with the same number of one-bit ADCs.

In the conventional information theoretic analysis of multiterminal communication scenarios, it is often assumed that all of the distributed terminals use the communication channel simultaneously. However, in practical wireless communication systems - due to restricted computation complexity at network terminals - a limited number of users can be activated either in uplink or downlink simultaneously. This necessitates the design of a scheduler which determines the set of active users at each time-slot. A well-designed scheduler maximizes the average system utility subject to a set of fairness criteria, which must be met in a limited window-length to avoid long starvation periods. In this work, scheduling under short-term temporal fairness constraints is considered. The objective is to maximize the average system utility such that the fraction of the time-slots that each user is activated is within desired upper and lower bounds in the fairness window-length. The set of feasible window-lengths is characterized as a function of system parameters. It is shown that the optimal system utility is non-monotonic and super-additive in window-length. Furthermore, a scheduling strategy is proposed which satisfies short-term fairness constraints for arbitrary window-lengths, and achieves optimal average system utility as the window-length is increased asymptotically. Numerical simulations are provided to verify the results.

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen's result [1] on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings.

A new class of structured codes called quasi group codes (QGCs) is introduced. A QGC is a subset of a group code. In contrast with the group codes, QGCs are not closed under group addition. The parameters of the QGC can be chosen, such that the size of C + C is equal to any number between C and |C|2. We analyze the performance of a specific class of QGCs. This class of QGCs is constructed by assigning single-letter distributions to the indices of the codewords in a group code. Then, the QGC is defined as the set of codewords whose index is in the typical set corresponding to these singleletter distributions. The asymptotic performance limits of this class of QGCs are characterized using single-letter information quantities. Corresponding covering and packing bounds are derived. It is shown that the point-to-point channel capacity and optimal rate-distortion function are achievable using QGCs. Coding strategies based on QGCs are introduced for three fundamental multi-terminal problems: the Körner-Marton problem for modulo prime-power sums, computation over the multiple access channel (MAC), and MAC with distributed states. For each problem, a single-letter achievable rate-region is derived. It is shown, through examples, that the coding strategies improve upon the previous strategies based on the unstructured codes, linear codes, and group codes.

In this paper we consider the information-theoretic characterization of performance limits of a broad class of multiterminal communication problems with general continuous-valued sources and channels. In particular, we consider point- to-point source coding and channel coding with side information, distributed source coding with distortion constraints and function reconstruction problems (two-help-one). We develop an approach that uses fine quantization of the source and the channel variables followed by random coding with unstructured as well as structured (linear) code ensembles. This approach leads to lattice-like codes for general sources and channels.

In this paper, we investigate the necessity of finite blocklength codes in distributed transmission of independent message sets over channels with feedback. We provide two examples of three user interference channels with feedback where codes with asymptotically large effective lengths are sub-optimal. As a result, we conclude that coded transmission using finite effective length codes is necessary to achieve optimality. We argue that the sub-optimal performance of large effective length codes is due to their inefficiency in preserving the correlation between the inputs to the distributed terminals in the communication system. This correlation is made available by the presence of feedback at the terminals and is used as a means for coordination between them when using finite effective length coding strategies.

In this paper, the problem of matching pairs of correlated random graphs with multi-valued edge attributes is considered. Graph matching problems of this nature arise in several settings of practical interest including social network de-anonymization, study of biological data, and web graphs. An achievable region of graph parameters for successful matching is derived by analyzing a new matching algorithm that we refer to as typicality matching. The algorithm operates by investigating the joint typicality of the adjacency matrices of the two correlated graphs. Our main result shows that the achievable region depends on the mutual information between the variables corresponding to the edge probabilities of the two graphs. The result is based on bounds on the typicality of permutations of sequences of random variables that might be of independent interest.

In this paper, de-anonymizing internet users by actively querying their group memberships in social networks is considered. An anonymous victim visits the attacker's website, and the attacker uses the victim's browser history to query her social media activity for the purpose of de-anonymization using the minimum number of queries. A stochastic model of the problem is considered where the attacker has partial prior knowledge of the group membership graph and receives noisy responses to its real-time queries. The victim's identity is assumed to be chosen randomly based on a given distribution which models the users' risk of visiting the malicious website. A de-anonymization algorithm is proposed which operates based on information thresholds and its performance both in the finite and asymptotically large social network regimes is analyzed. Furthermore, a converse result is provided which proves the optimality of the proposed attack strategy.

We consider the problem of multiple descriptions (MDs) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the l -descriptions problem was the combinatorial message sharing with binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning. In the first part of the paper, we show that this strategy can be improved upon using more general unstructured quantizers and a more general unstructured binning method. In the second part, structured coding strategies are considered. First, structured coding strategies are developed by considering the specific MD examples involving three or more descriptions. We show that the application of structured quantizers results in strict RD improvements when there are more than two descriptions. Furthermore, we show that a structured binning also yields improvements. These improvements are in addition to the ones derived in the first part of the paper. This suggests that structured coding is essential when coding over more than two descriptions. Using the ideas developed through these examples, we provide a new unified coding strategy by considering several structured coding layers. Finally, we characterize its performance in the form of an inner bound to the optimal RD region using computable single-letter information quantities. The new RD region strictly contains all of the previous known achievable regions.

In this paper, we establish a new inequality tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper-bound on the correlation between the outputs of these functions. The upper-bound is useful in various disciplines which deal with common-information. We build upon Witsenhausen's [2] bound on maximum-correlation. The previous upper-bound did not take the effective length of the Boolean functions into account. One possible application of the new bound is to characterize the communication-cooperation tradeoff in multi-terminal communications. In this problem, there are lower-bounds on the effective length of the Boolean functions due to the rate-distortion constraints in the problem, as well as lower bounds on the output correlation at different nodes due to the multi-terminal nature of the problem.

We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider BBCs which are generated randomly, and using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to upper-bound the correlation between the outputs of two distributed BBCs. Finally, the upper-bound is used to show that the large blocklength single-letter coding schemes in the literature are sub-optimal in some multiterminal communication settings.

The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-4 addition. It is shown that the sum rate R1+ R2=1 bits per channel use is achievable using the new scheme. Whereas, the natural extension of the Gel'fand-Pinsker scheme, sum-rates greater than 0.32 are not achievable.

The problem of three-user multiple-access channel (MAC) with noiseless feedback is investigated. A new coding strategy is presented. The coding scheme builds upon the natural extension of the Cover-Leung (CL) scheme [1]; and uses quasi-linear codes. A new single-letter achievable rate region is derived. The new achievable region strictly contains the CL region. This is shown through an example. In this example, the coding scheme achieves optimality in terms of transmission rates. It is shown that any optimality achieving scheme for this example must have a specific algebraic structure. Particularly, the codebooks must be closed under binary addition.

A new ensemble of structured codes is introduced. These codes are called Quasi Linear Codes (QLC). The QLC's are constructed by taking subsets of linear codes. They have a looser structure compared to linear codes and are not closed under addition. We argue that these codes provide gains in terms of achievable Rate-Distortions (RD) in different multi-terminal source coding problems. We derive the necessary covering bounds for analyzing the performance of QLC's. We then consider the Multiple-Descriptions (MD) problem, and prove through an example that the application of QLC's gives an improved achievable RD region for this problem. Finally, we derive an inner bound to the achievable RD region for the general MD problem which strictly contains all of the previous known achievable regions.

We consider the problem of coding over the multiuser Interference Channel (IC). It is well-known that aligning the interfering signals results in improved achievable rates in certain setups involving more than two users. We argue that in the general interference problem, senders face a tradeoff between communicating their message to their corresponding decoder or cooperating with other users by aligning their signals. Traditionally, interference alignment is carried out using structured codes such as linear codes and group codes. We show through an example that the usual structured coding schemes used for interference neutralization lack the necessary flexibility to optimize this tradeoff. Based on this intuition, we propose a new class of codes for this problem. We use the example to show that the application of these codes gives strict improvements in terms of achievable rates. Finally, we derive a new achievable region for the three user IC which strictly improves upon the previously known inner bounds for this problem.

The problem of three-user Multiple-Access Channel (MAC) with correlated sources is investigated. An extension to the Cover-El Gamal-Salehi (CES) scheme is introduced. We argue that if the sources impose certain algebraic structures, then the application of structured codes improves upon the CES scheme. Based on this notion, we use a combination of the CES scheme with linear codes, and propose a new coding strategy. We derive new sufficient conditions to transmit correlated sources reliably. We consider an example of a three-user MAC with binary inputs. Using this example, we show strict improvements over the CES scheme.

A new coding scheme for the L-descriptions problem is proposed. In particular we consider continuous sources and lattice quantizers. New covering and packing bounds for using nested lattices are derived. We prove through an example that using nested lattice quantizers instead of independently generated codebooks results in gains.

A new structured coding scheme based on transversal group codes is proposed. We investigate the information theoretic performance limits for this strategy in multi-terminal communications. Achievability results are derived for lossless reconstruction of sum of two sources. In addition, a new rate region is presented for the problem of computation over multiple access channel. We show that the application of the new coding strategy, results in strict gains in terms of achievable rates in both settings.

A multiple-descriptions (MD) coding strategy is proposed and an inner bound to the achievable rate-distortion region is derived for discrete memoryless sources. The scheme utilizes linear codes. It is shown in two different MD set-ups that the linear coding scheme achieves a larger rate-distortion region than previously known random coding strategies. Furthermore, it is shown via an example that the best known random coding scheme for the set-up can be improved by including additional randomly generated codebooks.

A new coding scheme for the distributed source coding problem for general discrete memoryless sources is presented. The scheme involves a two-layered coding strategy, the first layer code is of constant finite block-length whereas the second layer contains codes of block-length approaching infinity. It is argued that small block-length codes preserve correlations between sources more efficiently, while suffering rate-loss in a point-to-point compression perspective. Consequently, there is a sweet-spot for the length of the code. An achievable rate-distortion region is characterized using single-letter distributions. It is shown that this region strictly contains previous known achievable rate-distortion regions for the distributed source coding problem.

We introduce a scheme for the binary one-help-one distributed source coding problem using two layers of codes. The primary code is of constant finite block-length and the secondary code has a block-length approaching infinity. The achievable rate-distortion region for this scheme is derived for the binary one-help-one problem. It is shown that the scheme achieves the common component rate-distortion region in the case when the sources have a common component, while if a common component is not present (i.e. replaced with highly correlated functions of the two inputs) it improves upon existing achievable bounds. We show that as the block-length of the primary code is increased, the transmission rate required in the scheme decreases, reaches its minimum at some finite value and then increases. This phenomenon is not typically seen in traditional schemes used in multi-terminal source coding.

In this paper, we present a new method for variable elimination in systems of inequalities which is much faster than the Fourier-Motzkin Elimination (FME) method. In our method, a linear Diophantine problem is introduced which is dual to the original problem. The new Diophantine system is then solved, and the final result is calculated by finding the dual system of inequalities. This new method uses the algorithm Normaliz to find the Hilbert basis of the solution space of the given Diophantine problem. We introduce a problem in the interference channel with multiple nodes and solve it with this new method. Next, we generalize our method to all problems involving FME and compare the method with the previous method. Our method has many advantages in comparison to the previous method. It does not produce many of the redundant answers of the FME method. It also solves the whole problem in one step whereas the previous method uses a step by step approach in eliminating each auxiliary variable.

In this paper, a two-user discrete memoryless multiple-access channel (DM-MAC) with correlated channel states, each known at one of the encoders is considered, in which each encoder transmits independent messages and tries to cooperate with the other one. To consider cooperating encoders, it is assumed that each encoder strictly-causally receives and learns the other encoder's transmitted symbols and tries to cooperate with the other encoder by transmitting its message. Next, we study this channel in a special case; we assume that the common part of both states is known at both, hence encoders use this opportunity to get better rate region. For these scenarios, an achievable rate region is derived based on a combination of block-Markov encoding and Gel'fand-Pinsker coding techniques. Furthermore, the achievable rate region is established for the Gaussian channel, and it is shown that the capacity region is achieved in certain circumstances.