The Fourier representation for the uniform distribution over the Boolean cube has found numerous applications in algorithms and complexity analysis. Notably, in learning theory, the learnability of Disjunctive Normal Form (DNF) under the uniform and product distributions has been established through such representations. This paper makes three main contributions. First, it introduces a generalized Fourier expansion that can be used with any distribution $D$ through the representation of the distribution as a Bayesian network (BN). Second, it shows that the main algorithmic tools for learning with the Fourier representation that use membership queries to approximate functions by recovering their heavy Fourier coefficients, can be used with slight modifications with the generalized expansion. These results hold for any distribution. Third, it analyzes the $L_1$ spectral norm of conjunctions under the new expansion, showing that it is bounded for a class of distributions which can be represented by a difference-bounded tree BN, where a parent node in the BN representation can change the conditional expectation of a child node by at most $\alpha<0.5$. Lower bounds are presented to show that such constraints are necessary. Combining these contributions, the paper shows learnability of DNF with membership queries under difference-bounded tree BN.

Classical shadow tomography (CST) involves obtaining enough classical descriptions of an unknown state via quantum measurements to predict the outcome of a set of quantum observables. CST has numerous applications, particularly in algorithms that utilize quantum data for tasks such as learning, detection, and optimization. This paper introduces a new CST procedure that exponentially reduces the space complexity and quadratically improves the running time of CST with single-copy measurements. The approach utilizes a quantum-to-classical-to-quantum process to prepare quantum states that represent shadow snapshots, which can then be directly measured by the observables of interest. With that, calculating large matrix traces is avoided, resulting in improvements in running time and space complexity. The paper presents analyses of the proposed methods for CST, with Pauli measurements and Clifford circuits.

Gradient estimation is a central challenge in training parameterized quantum circuits ( PQCs) for hybrid quantum-classical optimization and learning problems. This difficulty arises from several factors, including the exponential dimensionality of the Hilbert spaces and the information loss in quantum measurements. Existing estimators, such as finite difference and the parameter shift rule, often fail to adequately address these challenges for certain classes of PQCs. In this work, we propose a novel gradient estimation framework that leverages the underlying Lie algebraic structure of PQCs, combined with the Hadamard test. By analyzing the differential of the matrix exponential in Lie algebras, we derive an expression for the gradient as a linear combination of expectation values obtained via Hadamard tests. The coefficients in this decomposition depend solely on the circuit's parameterization and can be computed efficiently. Also, these expectation values can be estimated using state-of-the-art shadow tomography techniques. Our approach enables efficient gradient estimation, requiring a number of measurement shots that scales logarithmically with the number of parameters, and with polynomial classical and quantum time. This is an exponential reduction in the measurement cost and a polynomial speed-up in time compared to existing works.

The reliability function of a channel is the maximum achievable exponential rate of decay of the error probability as a function of the transmission rate. In this work, we derive bounds on the reliability function of discrete memoryless multiple-access channels (MAC) with noiseless feedback. We show that our bounds are tight for a variety of MACs, such as m-ary additive and two independent point-to-point channels. The bounds are expressed in terms of a new information measure called “variable-length directed information”. The outer bound is proved by analyzing stochastic processes defined based on the entropy of the message, given the past channel’s outputs. Our method relies on tools from the theory of martingales, variable-length information measures, and a new technique called time pruning. We further propose a variable-length achievable scheme consisting of three phases: (i) data transmission, (ii) hybrid data-confirmation, and (iii) full confirmation. We show that two-phase-type schemes are strictly suboptimal in achieving the MAC’s reliability function. Moreover, we study the shape of the lower-bound and show that it increases linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. As side results, we derive an outer bound on the capacity of MAC with noiseless feedback and study a new problem involving a hybrid of hypothesis testing and data transmission.

This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept class$\mathcal{C}$scales as$O(\vert \mathcal{C}\vert)$. This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound to$O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)$, where$\mathcal{C}^*$is the set of extreme points of the convex closure of$\mathcal{C}$and$V_{\mathcal{C}^*}$is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling as$O\left(\log \left\vert\mathcal{C}^*\right\vert\right)$. Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.

Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of k-qubit quantum operators, i.e., operations applicable on only k out of d qubits. The problem is studied according to the quantum probably approximately correct (QPAC) model abiding by quantum mechanical laws such as no-cloning, state collapse, and measurement incompatibility. With the delicacy of quantum samples and the richness of quantum operations, one expects a significantly larger quantum sample complexity. This paper proves the contrary. We show that the quantum sample complexity of k-qubit quantum operations is comparable to the classical sample complexity of their counterparts (juntas), at least when $\frac{k}{d}\ll 1$. This is surprising, especially since sample duplication is prohibited, and measurement incompatibility would lead to an exponentially larger sample complexity with standard methods. Our approach is based on the Pauli decomposition of quantum operators and a technique called Quantum Shadow Sampling (QSS) to reduce the sample complexity exponentially. The results are proved by developing (i) a connection between the learning loss and the Pauli decomposition; (ii) a scalable QSS circuit for estimating the Pauli coefficients; and (iii) a quantum algorithm for learning $k$-qubit operators with sample complexity $O(\frac{k4^k}{\epsilon^2}\log d)$.

Many conventional learning algorithms rely on loss functions other than the natural 0-1 loss for computational efficiency and theoretical tractability. Among them are approaches based on absolute loss (L1 regression) and square loss (L2 regression). The first is proved to be an agnostic PAC learner for various important concept classes such as juntas, and half-spaces. On the other hand, the second is preferable because of its computational efficiency which is linear in the sample size. However, PAC learnability is still unknown as guarantees have been proved only under distributional restrictions. The question of whether L2 regression is an agnostic PAC learner for 0-1 loss has been open since 1993 and yet has to be answered. This paper resolves this problem for the junta class on the Boolean cube — proving agnostic PAC learning of k-juntas using L2 polynomial regression. Moreover, we present a new PAC learning algorithm based on the Boolean Fourier expansion with lower computational complexity. Fourier-based algorithms, such as Linial et al. (1993), have been used under distributional restrictions, such as uniform distribution. We show that with an appropriate change one can apply those algorithms in agnostic settings without any distributional assumption. We prove our results by connecting the PAC learning with 0-1 loss to the minimum mean square estimation (MMSE) problem. We derive an elegant upper bound on the 0-1 loss in terms of the MMSE error based on that, we show that the sign of the MMSE is a PAC learner for any concept class containing it.

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.

We study sequential probability assignment in the context of online learning under logarithmic loss and obtain tight lower and upper bounds for sequential minimax regret. Sequential minimax regret is defined as the minimum excess loss over data horizon$T$that a predictor incurs over the best expert in a class, when the samples are presented sequentially and adversarially. Our upper bounds are established by applying Bayesian averaging over a novel “smooth truncated covering” of the expert class. This allows us to obtain tight (minimax) upper bounds that subsume the best known non-constructive bounds in an algorithmic fashion. For lower bounds, we reduce the problem to analyzing the fixed design regret via a novel application of Shtarkov sum adapted to online learning. We demonstrate the effectiveness of our approach by establishing tight regret bounds for a wide range of expert classes. In particular, we fully characterize the regret of generalized linear function with worst Lipschitz transform functions when the parameters are restricted to a unit norm$\ell _{s}$($s\ge 2$) ball of dimension$d$. We show that the regret grows as$\Theta (d\log T)$when$d\le O(T^{s/(s+1)-\epsilon })$for all$\epsilon >0$(with precise constant 1 when$d\le e^{o(\log T)}$) and$\tilde {O}(T^{s/(s+1)})$when$d\ge \Omega (T^{s/(s+1)})$. Finally, we show that the Bayesian approach may not always be optimal if the support of the prior is included in the reference class itself.

There has been significant recent interest in quantum neural networks (QNNs), along with their applications in diverse domains. Current solutions for QNNs pose significant challenges concerning their scalability, ensuring that the postulates of quantum mechanics are satisfied and that the networks are physically realizable. The exponential state space of QNNs poses challenges for the scalability of training procedures. The no-cloning principle prohibits making multiple copies of training samples, and the measurement postulates lead to non-deterministic loss functions. Consequently, the physical realizability and efficiency of existing approaches that rely on repeated measurement of several copies of each sample for training QNNs are unclear. This paper presents a new model for QNNs that relies on band-limited Fourier expansions of transfer functions of quantum perceptrons (QPs) to design scalable training procedures. This training procedure is augmented with a randomized quantum stochastic gradient descent technique that eliminates the need for sample replication. We show that this training procedure converges to the true minima in expectation, even in the presence of non-determinism due to quantum measurement. Our solution has a number of important benefits: (i) using QPs with concentrated Fourier power spectrum, we show that the training procedure for QNNs can be made scalable; (ii) it eliminates the need for resampling, thus staying consistent with the no-cloning rule; and (iii) enhanced data efficiency for the overall training process since each data sample is processed once per epoch. We present a detailed theoretical foundation for our models and methods' scalability, accuracy, and data efficiency. We also validate the utility of our approach through a series of numerical experiments.

As a class of state-dependent channels, Markov channels have been long studied in information theory for characterizing the feedback capacity and error exponent. This paper studies a more general variant of such channels where the state evolves via a general stochastic process, not necessarily Markov or ergodic. The states are assumed to be unknown to the transmitter and the receiver, but the underlying probability distributions are known. For this setup, we derive an upper bound on the feedback error exponent and the feedback capacity with variable length codes (VLCs). The bounds are expressed in terms of the directed mutual information and directed relative entropy. The bounds on the error exponent reduce to Burnashev’s expression for discrete memoryless channels. Our method relies on tools from the theory of martingales to analyze a stochastic process defined based on the entropy of the message given the past channel’s outputs.

In source coding since Davisson’s seminal paper [1] various redundancy and regrets were thoroughly analyzed, from pointwise redundancy, to average and maximal minimax and maxmin regrets. Similarly, in online learning, there are various formulations of regrets that are grouped into fixed-design (when data is known in advance) and sequential. This position paper gives a brief overview of current formulations of regrets, and provides a thorough comparison of the sequential and fixed design formulations. Moreover, inspired by the source coding literature, new classes of regrets, from average to worst case minimax, are introduced. In particular, it is shown that the fixed design and sequential regrets are equal in the worst case and average sense when data is known in advance; but, in maximal sense (when maximizing over data), the former can be significantly smaller than the latter. Specifically, this paper proves that under logarithmic loss (i) for linear predictors the two maximal formulations are of the same order; and (ii) for linear threshold predictors, fixed design maximal regret is logarithmically smaller than the sequential one.

We study sequential general online regression, known also as sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving a general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.

We consider the task of faithfully simulating a distributed quantum measurement, wherein we provide a protocol for the three parties, Alice, Bob and Charlie, to simulate a repeated action of a distributed quantum measurement using a pair of non-product approximating measurements by Alice and Bob, followed by a stochastic mapping at Charlie. The objective of the protocol is to utilize minimum resources, in terms of classical bits needed by Alice and Bob to communicate their measurement outcomes to Charlie, and the common randomness shared among the three parties, while faithfully simulating independent repeated instances of the original measurement. To achieve this, we develop a mutual covering lemma and a technique for random binning of distributed quantum measurements, and, in turn, characterize a set of sufficient communication and common randomness rates required for asymptotic simulatability in terms of single-letter quantum information quantities. In the special case, where the Charlie’s action is restricted to a deterministic mapping, we develop a one-shot performance characterization of the distributed faithful simulation problem. Furthermore, using these results we address a distributed quantum rate-distortion problem, where we characterize the achievable rate distortion region through a single-letter inner bound. Finally, via a technique of single-letterization of multi-letter quantum information quantities, we provide an outer bound for the rate-distortion region.

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provablyasymptotically optimalfeature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms.

Autonomous unmanned aerial vehicles (UAVs) are essential for detecting and tracking specific events, such as automatic navigation. The intelligent monitoring of people’s social distances in crowds is one of the most significant events caused by the coronavirus. The virus is spreading more quickly among the crowds, and the disease cycle continues in congested areas. Due to the error that occurs when humans monitor their activity, an automated model is required to alert to social distance violations in crowds. As a result, this article proposes a two-step framework based on autonomous UAV videos, including human tracking and deep learning-based recognition of the crowd’s social distance. The deep architecture is a modified-fast and lightweight ShuffleNet learning structure. First, the Kalman filter is used to determine the positions of individuals, and then the modified ShuffleNet is used to refine the bounding boxes obtained and determine the social distance. The social distance is calculated using the initial refinement of the bounding box obtained during the tracking step and the scale in frames of the human body. The observed average accuracy, average processing time (APT), and processed frame per second (FPS) for three congestion datasets were 97.5%, 84 milliseconds, and 11.5 FPS, respectively. Real-time decision-making was achieved by reducing the size and resolution of the frames. Additionally, the frames were re-labeled to reduce the computational complexity associated with detecting social distancing. The experimental results demonstrated that the proposed method could operate more quickly and accurately on various resolution frames of UAV videos with difficult conditions.

A fundamental obstacle in learning information from data is the presence of nonlinear redundancies and dependencies in it. To address this, we propose a Fourier-based approach to extract relevant information in the supervised setting. We first develop a novel Fourier expansion for functions of correlated binary random variables. This expansion is a generalization of the standard Fourier analysis on the Boolean cube beyond product probability spaces. We further extend our Fourier analysis to stochastic mappings. As an important application of this analysis, we investigate learning with feature subset selection. We reformulate this problem in the Fourier domain and introduce a computationally efficient measure for selecting features. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear dependencies in the features-label relation. Via theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on our measure and verify our findings via numerical experiments on various datasets.

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 take an information-theoretic approach to identify nonlinear feature redundancies in unsupervised learning. We define a subset of features as sufficiently-informative when the joint entropy of all the input features equals that of the chosen subset. We argue that the rest of the features are redundant as all the accessible information about the data can be captured from sufficiently-informative features. Next, instead of directly estimating the entropy, we propose a Fourier-based characterization. For that, we develop a novel Fourier expansion on the Boolean cube incorporating correlated random variables. This generalization of the standard Fourier analysis is beyond product probability spaces. Based on our Fourier framework, we propose a measure of redundancy for features in the unsupervised settings. We then consider a variant of this measure with a search algorithm to reduce its computational complexity as low as$O$(nd) with$n$being the number of samples and$d$the number of features. Besides the theoretical justifications, we test our method on various real-world and synthetic datasets. Our numerical results demonstrate that the proposed method outperforms state-of-the-art feature selection techniques.

In this work, we study two problems: three-user Multiple-Access Channel (MAC) with correlated sources, and MAC with Feedback (MAC-FB) with independent messages. For the first problem, we identify a structure in the joint probability distribution of discrete memoryless sources, and define a new common information called “conferencing common information”. We develop a multi-user joint-source channel coding methodology based on structured mappings to encode this common information efficiently and to transmit it over a MAC. We derive a new set of sufficient conditions for this coding strategy using single-letter information quantities for arbitrary sources and channel distributions. Next, we make a fundamental connection between this problem and the problem of communication of independent messages over three-user MAC-FB. In the latter problem, although the messages are independent to begin with, they become progressively correlated given the channel output feedback. Subsequent communication can be modeled as transmission of correlated sources over MAC. Exploiting this connection, we develop a new coding scheme for the problem. We characterize its performance using single-letter information quantities, and derive an inner bound to the capacity region. For both problems, we provide a set of examples where these rate regions are shown to be optimal. Moreover, we analytically prove that this performance is not achievable using random unstructured random mappings/codes.

We investigate faithful simulation of distributed quantum measurements as an extension of Winter's measurement compression theorem. We characterize a set of communication and common randomness rates needed to provide faithful simulation of distributed measurements. To achieve this, we introduce binning and mutual packing lemma for distributed quantum measurements. These techniques can be viewed as the quantum counterpart of their classical analogues. Finally, using these results, we develop a distributed quantum-to-classical rate distortion theory and characterize a rate region analogous to Berger-Tung's in terms of single-letter quantum mutual information quantities.

This paper considers the problem of approximating a Boolean function f using another Boolean function from a specified class. Two classes of approximating functions are considered: k-juntas, and linear Boolean functions. The n input bits of the function are assumed to be independently drawn from a distribution that may be biased. The quality of approximation is measured by the mismatch probability between f and the approximating function g. For each class, the optimal approximation and the associated mismatch probability is characterized in terms of the biased Fourier expansion of f. The technique used to analyze the mismatch probability also yields an expression for the noise sensitivity of f in terms of the biased Fourier coefficients, under a general i.i.d. input perturbation model.

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 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.

We derive a lower and upper bounds on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we present a coding scheme consisting of a data and a confirmation stage. In the data stage, any arbitrary feedback capacity-achieving code is used. In the confirmation stage, each transmitter sends one bit of information to the receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are selected randomly according to an appropriately optimized joint probability distribution. The bounds increase linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. The lower and upper bounds match for a class of MACs.

The group capacity of a discrete memoryless channel$(\mathcal {X},\mathcal {Y},W_{Y|X})$is characterized with maximal probability of error in of[1, Sec. II]. There is a mistake in the proof of achievability as given in Section VII.A. It is correctly shown on page 2408–2409 that\begin{equation*} \lim _{n \rightarrow \infty } \max _{a} \mathbb {E} \left [{ P(E(a)) }\right ] =0 \end{equation*}if for all$\hat {\theta } \neq \boldsymbol {s}$,\begin{align*}&\hspace {-0.5pc}R \frac {\sum _{(p,s)\in \mathcal {S}(G)} (s- \hat {\theta }_{p,s}) w_{p,s} \log p}{\sum _{(p,s) \in \mathcal {S} (G)} s w_{p,s} \log q} \\&\qquad \qquad \quad \qquad <\log |H_{\eta ^{*}+\hat {\theta }}|-H(X_{\eta ^{*},b}|Y,[X_{\eta ^{*},b}]_{\hat {\theta }}) - O(\epsilon ). \end{align*}However it is incorrectly claimed that the achievability conditions are: for all$\hat {\theta } \neq \pmb {s}$,\begin{equation*} R\le \frac {1}{1-\omega _{\hat {\theta }}} I(X_{\eta ^{*},b};Y|[X_{\eta ^{*},b}]_{\hat {\theta }}). \end{equation*}Our original objective was to characterize the average error group capacity of a discrete memoryless channel. The average error is more widely used than the maximal error. Although we had the proof of achievability for the average error case, we could not prove the converse. So we settled for characterizing the maximal error group capacity. In light of the above error, we have the following resolution.

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.

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.

The problem of computing modulo prime-power sums is investigated in distributed source coding as well as computation over Multiple-Access Channel (MAC). We build upon group codes and present a new class of codes called Quasi Group Codes (QGC). A QGC is a subset of a group code. These codes are not closed under the group addition. We investigate some properties of QGC's, and provide a packing and a covering bound. Next, we use these bounds to derived achievable rates for distributed source coding as well as computation over MAC. We show that strict improvements over the previously known schemes can be obtained using QGC's.

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.