We undertake a Shannon theoretic study of the problem of communicating bit streams over a 3-user classical-quantum interference channel (3-CQIC) and focus on characterizing inner bounds. We design a new coding strategy based on (i) coset codes possessing algebraic closure properties and (ii) decoding POVMs to decode bi-variate interference efficiently. Needing to perform simultaneous decoding, we enhance Sen's powerful technique of tilting, smoothing, and augmentation - originally designed only for IID codes - to decode into `functions of codebooks'. Developing analysis techniques to combine all of these elements, we derive a new inner bound to the capacity region of a 3-CQIC. The derived inner bound subsumes all currently known inner bounds and is analytically proven to be strictly larger for identified examples, including non-commutative `additive' and `non-additive' ones.

We continue the study of the learnability of quantum measurement classes in the setting where the learner is given access only to prepared quantum states, aiming for necessary and sufficient conditions for PAC learnability, along with corresponding sample complexity bounds. In the quantum setting, in contrast with the classical probabilistically observed case, sampled states are perturbed when a quantum measurement is applied, according to the Born rule, so that distinct samples in the training data cannot be arbitrarily reused. We first probe the results from previous works on this setting. We show that the empirical risk defined in previous works and matching the definition in the classical theory can fail to satisfy the uniform convergence property enjoyed in the classical learning setting for classes that we can show to be PAC learnable. Moreover, we show that VC dimension generalization upper bounds in previous work are in many cases infinite, even for measurement classes defined on a finite-dimensional Hilbert space. We then show that, nonetheless, every measurement class defined on a finite-dimensional Hilbert space is PAC learnable via a modification of the ERM rule.

By developing a new framework of likelihood POVMs, analysis techniques and a new proof of the quantum covering lemma, we address the simulation of separable quantum measurement over bipartite states. In addition to a new one shot inner bound that naturally generalizes to the asymptotic case, we demonstrate the power, generality and universality of the developed techniques in the most general distributed measurement scenario by recovering all current known inner bounds. In addition to the above results, this framework is appealing in being the most natural and simple POVM simulation protocol.

We consider a scenario wherein two parties Alice and Bob are provided$X_{1}^{n}$and$X_{2}^{n}$– samples that are IID from a PMF$P_{X_{1} X_{2}}$. Alice and Bob can communicate to Charlie over (noiseless) communication links of rates$R_{1}$and$R_{2}$, respectively. Their goal is to enable Charlie generate samples$Y^{n}$such that the triple$(X_{1}^{n},X_{2}^{n},Y^{n})$has a PMF that is close, in total variation, to$\prod P_{X_{1} X_{2} Y}$, enabling the three parties achieve strong coordination. In addition, the three parties may posses pairwise shared common randomness at rates$C_{1}$and$C_{2}$. We address the problem of characterizing the set of rate quadruples$(R_{1},R_{2},C_{1},C_{2})$for which the above goal can be accomplished. We propose a new coding scheme based on random algebraic codes–coset codes in particular–of asymptotically large block-length. We analyze its performance and derive a single-letter information-theoretic inner bound. This bound subsumes the largest known inner bound and improves upon it strictly for identified examples. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic code ensembles. In addition, we provide an outer bound to the rate region for this three party distributed setup.

We formulate a quantum analogue of the fundamental classical PAC learning problem. As on a quantum computer, we model data to be encoded by modifying specific attributes - spin axis of an electron, plane of polarization of a photon - of sub-atomic particles. Any interaction, including reading off, extracting or learning from such data is via quantum measurements, thus leading us to a problem of PAC learning Quantum Measurement Classes. We propose and analyze the sample complexity of a new ERM algorithm that respects quantum non-commutativity. Our study entails that we define the VC dimension of Positive Operator Valued Measure(ments) (POVMs) concept classes. Our sample complexity bounds involve optimizing over partitions of jointly measurable classes. Finally, we identify universally consistent sequences of POVM classes. Technical components of this work include computations involving tensor products, trace and uniform convergence bounds.

This paper is eligible for the Jack Reil Wolf ISIT Student Paper Award.We prove new one shot achievability results for measurement compression of quantum instruments with side information at the receiver. Unlike previous one shot results for this problem, our one shot bounds are nearly optimal and do not need catalytic randomness. In fact, we state a more general problem called centralised multi link measurement compression with quantum side information and provide one shot achievability results for it. As a simple corollary, we obtain one shot measurement compression results for quantum instruments with side information that we mentioned earlier. All our one shot results lead to the standard results for this problem in the asymptotic iid setting. We prove our achievability bounds by first proving a novel sequential classical quantum multipartite covering lemma, which should be of independent interest.

We consider the problem of communicating over a classical-quantum (CQ) multiple access channel with classical state information non-causally available at the transmitters, henceforth referred to as a QMSTx. We undertake a Shannon-theoretic study and focus on the problem of characterizing inner bounds to the capacity region of a QMSTx. We propose a new coding scheme based on union coset codes - codes possessing algebraic closure properties and derive a new inner bound that subsumes the largest known inner bound based on IID random coding. We identify examples for which the derived inner bound is strictly larger.

We consider the scenario of communicating on a 3-user classical-quantum broadcast channel. We undertake an information theoretic study and focus on the problem of characterizing an inner bound to its capacity region. We design a new coding scheme based partitioned coset codes - an ensemble of codes possessing algebraic properties. Analyzing its information-theoretic performance, we characterize a new inner bound. We identify examples for which the derived inner bound is strictly larger than that achievable using IID random codes.

We consider the task of communicating a generic bivariate function of two classical correlated sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. We first propose a coding scheme based on asymptotically good algebraic structured codes, in particular, nested coset codes, and provide a set of sufficient conditions for the reconstruction of the function of the sources over a CQ-MAC. The proposed technique enables the decoder to recover the desired function without recovering the sources themselves. We further improve this by employing a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes. This coding scheme allows exploiting the symmetric structure common amongst the sources and also leverage the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources whose function can be reconstructed over any given CQ-MAC, and identify examples demonstrating the same. We provide these conditions in terms of single-letter quantum information-theoretic quantities.

We consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. Building on the techniques developed for the case of a classical channel, we propose and analyze a coding scheme based on coset codes. The proposed technique enables the decoder recover the desired function without recovering the sources themselves. We derive a new set of sufficient conditions that are weaker than the current known for identified examples. This work is based on a new ensemble of coset codes that are proven to achieve the capacity of a classical-quantum point-to-point channel.

We consider the problem of characterizing an inner bound to the capacity region of a 3—user classical-quantum interference channel (3—CQIC). The best known coding scheme for communicating over CQICs is based on unstructured random codes and employs the techniques of message splitting and superposition coding. For classical 3—user interference channels (ICs), it has been proven that coding techniques based on coset codes - codes possessing algebraic closure properties - strictly outperform all coding techniques based on unstructured codes. In this work, we develop analogous techniques based on coset codes for 3to1—CQICs - a subclass of 3—user CQICs. We analyze its performance and derive a new inner bound to the capacity region of 3to1—CQICs that subsume the current known largest and strictly enlarges the same for identified examples.

In this problem, Alice and Bob, are provided$X_{1}^{n}$and$X_{2}^{n}$that are IID$px_{1}x_{2}$. Alice and Bob can communicate to Charles over (noiseless) links of rate$R_{1}$and$R_{2}$, respectively. Their goal is to enable Charles generate samples$Y^{n}$such that the triple$(X_{1}^{n},\ X_{2}^{n},\ Y^{n})$has a PMF that is close, in total variation, to$\prod p_{X_{1}X_{2}\mathrm{Y}}$. In addition, the three parties may posses shared common randomness at rate$C$. We address the problem of characterizing the set of rate triples$(R_{1},\ R_{2},\ C)$for which the above goal can be accomplished. We build on our recent findings and propose a new coding scheme based on coset codes. We analyze its information-theoretic performance and derive a new inner bound. We identify examples for which the derived inner bound is analytically proven to contain rate triples that are not achievable via any known unstructured code based coding techniques. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic structured code ensembles. This adds to the advancement of the use structured codes in network information theory.

Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.

We present the second part of our work on communicating correlated sources over multiple access (MAC) and interference channels (IC). Specifically, we undertake a Shannon-theoretic study of the above scenarios and focus on characterizing sufficient conditions for lossless recoverability of the sources at the decoder(s). We enhance the fixed block-length (B-L) coding technique by incorporating the technique of inducing source correlation onto channel inputs, originally discovered by Cover, El Gamal and Salehi. In contrast to the first part, performance analysis of a joint source-channel decoder poses new challenges. We enhance the earlier developed suite of coding and analytical tools to overcome these challenges and derive (simplified) single-letter characterizations for a new set of sufficient conditions for both scenarios. For both the MAC and IC problems, the derived sufficient conditions are (i) subsumed in the current known tightest, and (ii) strictly weaker for identified examples. Lastly, we propose simple `plug-in' approaches that can further weaken the derived sufficient conditions. Our findings enable us to subsume Dueck's findings (1981) and go even further for the example considered therein.

We consider a scenario wherein two parties Alice and Bob are provided X1nand X2n-samples that are IID from a PMF pX1X2. Alice and Bob can communicate to Charles over (noiseless) communication links of rate R1and R2respectively. Their goal is to enable Charles generate samples Ynsuch that the triple (X1n, X2nYn). In addition, the three parties may posses shared common randomness at rate C. We address the problem of characterizing the set of rate triples (R1, R2, C) for which the above goal can be accomplished. We provide a set of sufficient conditions, i.e., an achievable rate region for this three party setup. Our work also provides a complete characterization of a point-to-point setup wherein Bob is absent and Charles is provided with side-information.

We consider the two scenarios of communicating a pair S1, S2of distributed correlated sources over 2-user multiple access (MAC) and interference channels (IC), respectively. While in the MAC problem, the receiver needs to reconstruct both sources, in the IC problem, receiver j needs to reconstruct S3.We undertake a Shannon theoretic study and focus on characterizing sufficient conditions. Building on Dueck's findings (1981), we propose a coding scheme based on fixed block-length (B-L) codes. We characterize its information theoretic performance and characterize a new set of sufficient conditions. We identify examples of the MAC and IC problems for which the latter conditions are proven to be strictly weaker than the current known tightest.

As an increasing amount of data is gathered nowadays and stored in databases, the question arises of how to protect the privacy of individual records in a database even while providing accurate answers to queries on the database. Differential Privacy (DP) has gained acceptance as a framework to quantify vulnerability of algorithms to privacy breaches. We consider the problem of how to sanitize an entire database via a DP mechanism, on which unlimited further querying is performed. While protecting privacy, it is important that the sanitized database still provide accurate responses to queries. The central contribution of this work is to characterize the amount of information preserved in an optimal DP database sanitizing mechanism (DSM). We precisely characterize the utility-privacy trade-off of mechanisms that sanitize databases in the asymptotic regime of large databases. We study this in an information-theoretic framework by modeling a generic distribution on the data, and a measure of fidelity between the histograms of the original and sanitized databases. We consider the popular L1-distortion metric, i.e., the total variation norm that leads to the formulation as a linear program (LP). This optimization problem is prohibitive in complexity with the number of constraints growing exponentially in the parameters of the problem. Our focus on the asymptotic regime enables us characterize precisely, the limit of the sequence of solutions to this optimization problem. Leveraging tools from discrete geometry, analytic combinatorics, and duality theorems of optimization, we fully characterize this limit in terms of a power series whose coefficients are the number of integer points on a multidimensional convex crosspolytope studied by Ehrhart in 1967. Employing Ehrhart theory, we determine a simple closed form computable expression for the asymptotic growth of the optimal privacy-fidelity trade-off to infinite precision. At the heart of the findings is a deep connection between the minimum expected distortion and a fundamental construct in Ehrhart theory - Ehrhart series of an integral convex polytope.

We derive a new inner bound to the rate-distortion (RD) region of the robust distributed source coding (RDSC) problem. The derived bound is proven to strictly enlarge the previous known largest for identified examples. This builds on the fixed block-length coding scheme that has been proposed in a series of recent works. Detailed results are available in [1].

We enhance the fixed block-length coding scheme for joint source channel coding over MAC and IC. We prove that this enhancement yields strictly weaker sufficient conditions for both problems.

We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the L1-distortion between the histograms of original and sanitized databases, while being θ-differentially private (DP). The expected L1-distortion of a corresponding optimal θ-DP DSM provides for an important utility-privacy trade-off. This problem reduces to a prohibitively complex linear program (LP). Using tools from Ehrhart theory, analytic combinatorics and LP theory, we solve this problem and thereby provide a simple closed form computable expression characterizing this trade-off.

We consider the problem of developing coding techniques and deriving achievable rate regions for discrete memoryless broadcast channels with three receivers (3-DBC). We begin by identifying a novel vector additive 3-DBC for which we characterize an upper bound on the the largest achievable rate region based on unstructured codes, henceforth referred to as 1 M-region. We propose a coding technique based on coset codes that yield an achievable rate triple not contained within 1 M-region. We generalize the proposed coding technique using a new ensemble of codes-partitioned coset codes (PCC)-containing both empirical and algebraic properties, and evaluate its performance to derive an achievable rate region for the general 3-DBC. The new elements in this derivation are binning and joint typicality encoding and decoding of statistically correlated PCCs. We validate the utility of this technique by identifying non-additive instances of 3-DBC for which the proposed coding techniques based on PCC yield strictly larger rates.

A new coding technique, based on fixed block-length codes, is proposed for the problem of communicating a pair of correlated sources over a 2-user interference channel. Its performance is analyzed to derive a new set of sufficient conditions. The latter is proven to be strictly less binding than the current known best, which is due to Liu and Chen [1]. Our findings are inspired by Dueck's example [2].

The problem of characterizing sufficient conditions for communicating correlated sources over a MAC is considered. The technique of inducing source correlation onto channel inputs [1] is enhanced by the use of fixed B-L coding [2]. The performance of the proposed coding technique is characterized via single-letter expressions to derive a new set of sufficient conditions. The latter conditions are contained within those characterized in [1], and are proven to be strictly less binding than those of the latter for certain examples.

The joint source-channel coding problem of transmitting a pair of correlated sources over a 2-user MAC is considered. A new concatenated coding scheme, comprising of an inner code of fixed block-length and an outer code of arbitrarily large block-length, is proposed. Its information theoretic performance is analyzed to derive a new set of sufficient conditions. An example is identified to demonstrate that the proposed coding technique can strictly outperform the current known best, which is due to Cover, El Gamal and Salehi. Our findings are based on Dueck's ingenious coding technique proposed for the particular example studied in the work of Dueck (1981).

We consider the problem of communication over a three-user discrete memoryless interference channel (3-IC). The current known coding techniques for communicating over an arbitrary 3-IC are based on message splitting, superposition coding, and binning using independent and identically distributed (i.i.d.) random codebooks. In this paper, we propose a new ensemble of codes-partitioned coset codes (PCCs)-that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit the algebraic closure property of PCC to enable interference alignment over general 3-IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete 3-IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, moreover, strictly larger than the current known largest achievable rate regions based on the i.i.d. random codebooks.

We present a case for the use of codes possessing algebraic closure properties - coset codes - in developing coding techniques and characterizing achievable rate regions for generic multi-terminal channels. In particular, we consider three diverse communication scenarios - 3-user interference channel (many-to-many), 3-user broadcast channel (one-to-many), and multiple access with distributed states (many-to-one) - and identify non-additive examples for which coset codes are analytically proven to yield strictly larger achievable rate regions than those achievable using IID codes. On the one hand, our findings motivate the need for multi-terminal information theory to step beyond IID codes. On the other, it encourages current research of linear code-based techniques to go beyond particular additive communication channels. Detailed proofs of our results are available in [1]-[3].

The problem of computing sum of sources over a multiple access channel (MAC) is considered. Building on the technique of linear computation coding (LCC) proposed by Nazer and Gastpar [1], we employ the ensemble of nested coset codes to derive a new set of sufficient conditions for computing sum of sources over an arbitrary MAC. The optimality of nested coset codes [2] enables this technique outperform LCC even for linear MAC with a structural match. Examples of non-additive MAC for which the technique proposed herein outperforms separation and systematic based computation are also presented. Finally, this technique is enhanced by incorporating separation based strategy, leading to a new set of sufficient conditions for computing sum over a MAC.

We present an achievable rate region for the general three user discrete broadcast channel (DBC), based on coset codes. We identify an example of a three user DBC for which the proposed achievable rate region strictly enlarges that obtained by a natural extension of Marton's [1] rate region. As a step towards deriving the achievable rate region for the general three user DBC, we characterize and derive an achievable rate region for a new class - 3-to-1 DBC- of broadcast channels of which the aforementioned is an example.

We prove that the ensemble of the nested coset codes built on finite fields achieves the capacity of arbitrary discrete memoryless point-to-point channels. Exploiting its algebraic structure, we develop a coding technique for communication over general discrete multiple access channel with channel state information distributed noncausally at the transmitters. We build an algebraic coding framework for this problem using the ensemble of Abelian group codes and, thereby, derive a new achievable rate region. We identify non-additive and non-symmetric examples for which the proposed achievable rate region is strictly larger than the one achievable using random unstructured codes.

The 3-user discrete memoryless interference channel is considered in this paper. We provide a new inner bound (achievable rate region) to the capacity region for this channel. This inner bound is based on a new class of code ensembles based on asymptotically good nested linear codes. This achievable region is strictly superior to the straightforward extension of Han-Kobayashi rate region from the case of two-users to three-users. This rate region is characterized using single-letter information quantities. We consider examples to illustrate the rate region.

In several multi-terminal communication systems, it has been noted that the average performance of linear code ensemble is better than that of the standard unstructured code ensemble. However, it is well-known that linear code ensembles cannot achieve the point-to-point capacity of an arbitrary discrete memoryless channel. In this paper, we study nested linear codes and prove they achieve capacity of arbitrary discrete memoryless point to point channel with and without channel state information at the transmitter. Furthermore, we prove nested linear codes achieve Marton's inner bound, the largest known inner bound for the general discrete broadcast channel.

Rate-constrained power minimization (PMIN) over a code division multiple-access (CDMA) channel with correlated noise is studied. PMIN is shown to be an instance of a separable convex optimization problem subject to linear ascending constraints. PMIN is further reduced to a dual problem of sumrate maximization (RMAX). The results highlight the underlying unity between PMIN, RMAX, and a problem closely related to PMIN but with linear receiver constraints. Subsequently, conceptually simple sequence design algorithms are proposed to explicitly identify an assignment of sequences and powers that solve PMIN. The algorithms yield an upper bound of 2N - 1 on the number of distinct sequences where N is the processing gain. The sequences generated using the proposed algorithms are in general real-valued. If a rate-splitting and multi-dimensional CDMA approach is allowed, the upper bound reduces to N distinct sequences, in which case the sequences can form an orthogonal set and be binary plusmn1-valued.

Two decision versions of a combinatorial power minimization problem for scheduling in a time-slotted Gaussian multiple-access channel (GMAC) are studied in this paper. If the number of slots per second is a variable, the problem is shown to be NP-complete. If the number of time-slots per second is fixed, an algorithm that terminates in O (Length (I)N+1) steps is provided.

Sequence design problems are considered in this paper. The problem of sum power minimization in a spread spectrum system can be reduced to the problem of sum capacity maximization, and vice versa. A solution to one of the problems yields a solution to the other. Subsequently, conceptually simple sequence design algorithms known to hold for the white-noise case are extended to the colored noise case. The algorithms yield an upper bound of 2N - L on the number of sequences where N is the processing gain and L the number of non-interfering subsets of users. If some users (at most N - 1) are allowed to signal along a limited number of multiple dimensions, then N orthogonal sequences suffice.