Contributed and Invited Presentations

In this paper we deal with polar code automorphisms that are beneficial under low-latency automorphism ensemble (AE) decoding, and we propose polar code designs that have such automorphisms. Successive-cancellation (SC) decoding and thus SC-based AE decoding are invariant with respect to the only known polar code automorphisms, namely those of the lower-triangular affine (LTA) group. To overcome this problem, we provide methods to determine whether a given polar code has non-LTA automorphisms and to identify such automorphisms. Building on this, we design specific polar codes that admit automorphisms in the upper-diagonal linear (UTL) group, and thus render SC-based AE decoding effective. Demonstrated by examples, these new polar codes under AE decoding outperform conventional polar codes under SC list decoding in terms of error rate, while keeping the latency comparable to SC decoding. Moreover, state-of-the-art BP-based permutation decoding for polar codes is beaten by BP-based AE thanks to this design.

We combine polar and LDPC codes to address data correction for various low-power applications. We first use long low-rate LDPC codes that have parity checks of a low weight. Decoding performs several iterations of the belief propagation (BP) algorithm that recalculates the information bits only. Partially corrected bits are then passed to a short polar code that uses successive cancellation list (SCL) decoder. The newly corrected bits then serve as the new inputs for an LDPC decoder. For codes of rate less than 0.1, the algorithm performs on par with a SCL decoder, while substantially reducing decoding complexity and its latency.

In this work, we present a polar code design that offers a provably optimal solution for biometric identification systems allowing authentication under noisy enrollment with secrecy and privacy constraints. Binary symmetric memoryless source and channels are considered. It is shown that the proposed polar code design achieves the fundamental limits and satisfies more stringent secrecy constraints than previously in the literature. The proposed polar code design provides the first example of a code design that achieves the fundamental limits involving both identification and authentication.

Sampling from the lattice Gaussian distribution has emerged as a key problem in coding, decoding and cryptography. In this paper, the Gibbs sampling from Markov chain Monte Carlo (MCMC) methods is investigated for lattice Gaussian sampling. Firstly, the error function of random scan Gibbs sampling is derived, and we show that it is partially determined by the selection probabilities over the sampling components. Then, in order to minimize the error function for a better sampling performance, a reinforcement learning mechanism is proposed for random scan Gibbs sampling to adaptively update the selection probabilities by learning from the random samples generated along with the chain. Finally, simulation results based on MIMO detection are presented to confirm the performance gain at the expense of limited complexity cost.

We consider a novel multi-armed bandit setup in which the reward distribution of each arm depends on a single discrete Markov process. This setup involves correlation among arms, as well as correlation among each time instant when one of the arms is pulled. For this problem we show that the cumulative regret has to grow linearly with the number of instances where the outcome of the previous arm pull cannot be determined {\em uniquely}. We propose an algorithm relying on the empirical transition matrix and analyze its performance. The algorithm is shown to ensure that the contribution of regret from time instances where the outcome of the previous arm pull can be identified uniquely is minimized. This implies that the algorithm performs order-wise optimally. We experimentally show that our algorithm can perform better than the correlated-UCB algorithm introduced by Gupta et. al. in 2018 and the classical UCB algorithm.

The Good-Turing (GT) estimator is perhaps the most popular framework for modelling large alphabet distributions. Classical results show that the GT estimator convergences to the occupancy probability, formally defined as the total probability of words that appear exactly k times in the sample. In this work we introduce new convergence guarantees for the GT estimator, based on worst-case MSE analysis. Our results refine and improve upon currently known bounds. Importantly, we introduce a simultaneous convergence rate to the entire collection of occupancy probabilities.

We consider the unsourced random access based on a coded compressed sensing approach. The main idea is to replace the outer tree code proposed by Amalladinne et al. with the code capable of correcting t errors. We derive a finite-length random coding bound for such codes and suggest a practical code construction. We have conducted numerical experiments in the single antenna quasi-static Rayleigh fading MAC. The results show that transition to list-recoverable codes correcting t errors allows performance improvement of coded compressed sensing scheme by 7-10 dB compared to the tree code-based scheme.

We consider a discrete memoryless cloud radio access network in which K users communicate with a remote destination through 2 relays in a cascade. The relays are oblivious in the sense that they operate without knowledge of the users' codebooks. We focus on a scenario where the first and second relays are connected through a finite-capacity error-free link, while the second relay is connected to the remote destination via an infinite-capacity link. We establish the capacity region in this case, and show that it is achieved via a compress-and-forward scheme with successive decoding. Finally, the extension to Gaussian networks is discussed.

This paper analyses the multiplexing gain (MG) achievable over Wyner's symmetric network with random user activity and random arrival of mixed-delay traffic. The mixed-delay traffic is composed of delay-tolerant traffic and delay-sensitive traffic where only the former can benefit from transmitter and receiver cooperation since the latter is subject to stringent decoding delays. The total number of cooperation rounds at transmitter and receiver sides is limited to D rounds. We derive inner and outer bounds on the MG region. In the limit as D \to \infty, the bounds coincide and the results show that transmitting delay-sensitive messages does not cause any penalty on the sum MG. For finite D our bounds are still close and prove that the penalty caused by delay-sensitive transmissions is small.

Explicit assumption of stochastic data generative models is a remarkable feature of lossless compression of general data in information theory. However, current lossless image coding mostly focus on coding procedures without explicit assumption of the stochastic generative model. Therefore, we have difficulty discussing the theoretical optimality of the coding procedure to the stochastic generative model. In this paper, we solve this difficulty by constructing a stochastic generative model by interpreting the previous coding procedure from another perspective. An important problem of our approach is how to learn the hyperparameters of the stochastic generative model because the optimality of our coding algorithm is guaranteed only asymptotically and the hyperparameter setting still affects the expected code length for finite length data. For this problem, we use Bayesian hierarchical modeling and confirm its effect by numerical experiments. In lossless image coding, this is the first study assuming such an explicit stochastic generative model and learning its hyperparameters, to the best of our knowledge.

We introduce a tunable GAN, called .\alpha.-GAN, parameterized by .\alpha \in (0,\infty]., which interpolates between various .f.-GANs and Integral Probability Metric based GANs (under constrained discriminator set). We construct .\alpha.-GAN using a supervised loss function, namely, .\alpha.-loss, which is a tunable loss function capturing several canonical losses. We show that .\alpha.-GAN is intimately related to the Arimoto divergence, which was first proposed by \"{O}sterriecher (1996), and Liese and Vajda (2006). We posit that the holistic understanding that .\alpha.-GAN introduces will have practical benefits such as convergence and mode collapse.

Adversarial examples have recently exposed the severe vulnerability of neural network models. However, most of the existing attacks require some form of target model information (i.e., weights/model inquiry/architecture) to improve the efficacy of the attack. We leverage the information-theoretic connections between robust learning and generalized rate-distortion theory to formulate a universal adversarial example (UAE) generation algorithm. Our algorithm trains an offline adversarial generator to minimize the mutual information between the label and perturbed data. At the inference phase, our UAE method can efficiently generate effective adversarial examples without high computation cost. These adversarial examples in turn allow for developing universal defenses through adversarial training. Our experiments demonstrate promising gains in improving the training efficiency of conventional adversarial training.

Recently, a variant of the Reed-Muller family, called symmetric Reed-Muller codes, was proposed. In this paper, we prove that multivariable symmetric Reed-Muller codes form a class of locally-correctable codes. Then, the dual codes of symmetric Reed-Muller codes are given.

We consider low-complexity decoding of generalized second-order Reed-Muller frames. Second-order Reed-Muller frames are highly non-coherent, highly-structured, sets of 2^m-dimensional complex vectors with fourth root-of-unity alphabet, that come by design with a low-complexity chirp reconstruction algorithm (ChirpRA). In this paper, we extend ChirpRA to expanded frames in 2^m-dimension with same alphabet, and we also generalized it to Reed-Muller frames in other dimensions constructed from different alphabets.

We consider a semi-deterministic wiretap channel where the main channel is noiseless and the eavesdropper's channel is a binary erasure channel (BEC). We provide a lower bound for the achievable secrecy rates of polar and Reed-Muller codes, and compare it to the second order coding rate. To the best of our knowledge, this is the first work which demonstrates the secrecy performance of polar and Reed-Muller codes in short blocklengths. The results show that under a total variation secrecy metric, Reed-Muller codes can achieve secrecy rates very close to the second order approximation rate. On the other hand, we observe a significant gap between the lower bound for the achievable rates of polar codes and the the second order approximation rate for short blocklengths.

This paper studies lower bounds on the capacity of the relay channel with orthogonal receiver components (also referred to as primitive relay channel). We show that the lower bound in Theorem 7 of Cover and El Gamal, which uses mixed decode-forward and compress-forward strategies, is identical to the lower bound of Chong, Motani and Garg, and is always larger than or equal to the recent lower bound of Mondelli, Hassani and Urbanke. We provide a simplified expression for the lower bound in Theorem 7 of Cover and El Gamal and interpret one of its auxiliary variables as implementing the randomized time-sharing strategy. Next, we compare the lower bound for the Gaussian relay channel with orthogonal receiver components to existing upper bounds. Finally, we disprove a conjecture by Ahlswede and Han on the capacity of the subclass of relay channels with orthogonal receiver components and i.i.d. output.

Feedback is shown to increase the sum-rate capacity of K-user Gaussian multiple-access channels by at most a factor of approximately 1.54, improving Thomas' doubling bound (1987). The new bound is the best possible in the sense that it can be approached as closely as desired for a massive number of users. Moreover, feedback provides unbounded power gain in K for a fixed transmit power per user.

We pose and investigate the distributed secure source coding based on the common key cryptosystem. This cryptosystem includes the secrecy amplification problem for distributed encrypted sources with correlated keys using post-encryption-compression, which was posed investigated by Santoso and Oohama. In this paper we propose another new security criterion which is generally more strict compared with the commonly used security criterion which is based on the upper-bound of mutual information between the plaintext and the ciphertext. Under this criterion, we establish the necessary and sufficient condition for the secure transmission of correlated sources.

We design short blocklength codes for the Gaussian wiretap channel under information-theoretic security guarantees. Our approach consists in decoupling the reliability and secrecy constraints in our code design. Specifically, we handle the reliability constraint via an autoencoder, and handle the secrecy constraint via hash functions. For blocklengths smaller than 16, we evaluate through simulations the probability of error at the legitimate receiver and the leakage at the eavesdropper of our code construction. This leakage is defined as the mutual information between the confidential message and the eavesdropper's channel observations, and is empirically measured via a recent mutual information neural estimator. Simulation results provide examples of codes with positive rates that achieve a leakage inferior to one percent of the message length.

This paper considers Deep Neural Network (DNN) linear-nonlinear computations implemented on memristor crossbar substrates. To address the case where true memristor conductance values may differ from their target values, it introduces a theoretical framework that characterizes the effect of conductance value variations on the final inference computation. With only second-order moment assumptions, theoretical results on tracking the mean, variance, and covariance of the layer-by-layer noisy computations are given. By allowing the possibility of amplifying certain signals within the DNN, power consumption is characterized and then optimized via KKT conditions. Simulation results verify the accuracy of the proposed analysis and demonstrate the significant power efficiency gains that are possible via optimization for a target mean squared error.

The Gilbert-Elliot (GE) channel is a commonly-accepted model for packet erasures in networks. Streaming codes are a class of packet-level erasure codes designed to provide reliable communication over the GE channel. The design of a streaming code may be viewed as a two-step process. In the first, a more tractable, delay-constrained sliding window (DCSW) channel model is considered as a proxy to the GE channel. The streaming code is then designed to reliably recover from all erasures introduced by the DCSW channel model. Simulation is typically used to evaluate the performance of the streaming code over the original GE channel, as analytic performance evaluation is challenging. In the present paper, we take an important first step towards analytical performance evaluation. Recognizing that most, efficient constructions of a streaming code are based on the diagonal embedding or horizontal embedding of scalar block codes within a packet stream, this paper provides upper and lower bounds on the block-erasure probability of the underlying scalar block code when operated over the GE channel.

In this paper, we investigate streaming codes over a three-node relay network. Source node transmits a sequence of message packets to the destination via a relay. Source-to-relay and relay-to-destination links are unreliable and introduce at most N_1 and N_2 packet erasures, respectively. Destination needs to recover each message packet with a strict decoding delay constraint of T time slots. We propose streaming codes under this setting for all feasible parameters \{N_1, N_2, T\}. Relay naturally observes erasure patterns occurring in the source-to-relay link. In our code construction, we employ a channel-state-dependent relaying strategy, which rely on these observations. In a recent work, Fong et al. provide streaming codes featuring channel-state-independent relaying strategies, for all feasible parameters \{N_1, N_2, T\}. Our schemes offer a strict rate improvement over the schemes proposed by Fong et al., whenever N_1

Streaming codes may be regarded as packet-level convolutional codes that guarantee recovery from packet erasures under a strict decoding-delay constraint and are hence relevant to the low-latency objective of many modern communication systems. Past study of these codes has focused on performance over a tractable approximation of the Gilbert-Elliott channel model, known as the delay-constrained sliding window (DCSW) channel model. Under the DCSW channel model, within any sliding window of length w there can either be (i) a burst of at most b packet erasures or (ii) at most a random packet erasures. We study here, an extended version of the first constraint which permits e random erasures in addition to a burst of b erasures. We show that the capacity of this extended DCSW channel is strictly less than that of the corresponding DCSW channel in which b is replaced by b + e. Cyclic codes are easy to implement and are inherently well-suited to burst-erasure recovery. We identify a necessary and sufficient condition on the parity polynomial of an [n, k] cyclic code that allows the code to recover from any burst of n − k − s erasures along with any ρ random erasures, 1 ≤ ρ ≤ s ≤ n − k. We use this result to construct cyclic codes that provide reliable communication over the extended DCSW channel for certain parameters.

Universal coding of integers (UCI) is a class of variable-length code, such that the ratio of the expected codeword length to max{1, H(P)} is within a constant factor, where H(P) is the Shannon entropy of the decreasing probability distribution P. However, if we consider the ratio of the expected codeword length to H(P), the ratio tends to infinity by using UCI, when H(P) tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized UCI, such that the ratio of the expected codeword length to H(P) is within a constant factor K. The definition of generalized UCI is proposed, and then the coding structure of generalized UCI is introduced. Finally, the asymptotically optimal generalized UCI is presented.

The achievable rate region of Wyner-Ahlswede-Korner coding problem is investigated for mixed sources. Wyner-Ahlswede-Korner coding problem consists of two encoders and one decoder for two correlated sources. We derive the single-letter formula for mixed sources from Miyake and Kanaya's general result. It clarifies the behaviour of the Wyner-Ahlswede-Korner achievable region for non-ergodic sources; depending on the property of side-information, the achievable regions are different.

Although n-channel prefix-free codes are natural extensions of their 1-channel counterpart, the extra dimensions greatly increase the complexity of the problem such that most classical results cannot be generalized directly. Recently, a greedy algorithm was developed for deciding if it is possible to construct a 2-channel prefix-free code from a given multiset of codeword lengths. By dropping the information about codeword assignments which are not necessary for the decision problem, the greedy algorithm runs in polynomial time. However, if we naively turn the decision algorithm into a search algorithm (for constructing a prefix-free code) by retaining the information about codeword assignments, the computational complexity becomes exponential. One puzzle left unsolved was that whether the search problem can also be solved in polynomial time. In this paper, we give an affirmative answer to this question by designing a tailor-made data structure and a new lazy evaluation technique.

We study the problem of transmitting a sequence of messages (streaming messages) through a multi-link, multi-hop packet erasure network. Each message must be reconstructed in-order and under a strict delay constraint. Special cases of our setting with a single link on each hop have been studied recently - the case of a single relay-node, is studied in Fong et al [1]; the case of multiple relays, is studied in Domanovitz et al [2]. As our main result, we propose an achievable rate expression that reduces to previously known results when specialized to their respective settings. Our proposed scheme is based on the idea of concatenating single-link codes from [2] in a judicious manner to achieve the required delay constraints. We propose a systematic approach based on convex optimization to maximize the achievable rate in our framework.

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a \([\tau+1,\tau+1-a]\) Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from \(a\) arbitrary packet erasures, under a strict decoding delay constraint \(\tau\). Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of \(a\) erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from \(a>1\) arbitrary packet erasures under a decoding delay \(\tau\), have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay \(r<\tau\). We term these codes as \((a, \tau, r)\) locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters \(\{a, \tau, r\}\). Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our \((a, \tau=a(r+1)-1, r)\) LRSC construction provides the additional guarantee of recovery from the erasure of \(h, 1 \leq h \leq a,\) packets, with delay \(h(r+1)-1\). The construction thus offers graceful degradation in decoding delay with increasing number of erasures.

We consider a variant of the channel simulation problem with a single input and multiple outputs, where Alice observes a probability distribution \(P\) from a set of prescribed probability distributions \(\mathbb{\mathcal{P}}\), and sends a prefix-free codeword \(W\) to Bob to allow him to generate \(n\) i.i.d. random variables \(X_{1}, X_{2}, .., X_{n}\) which follow the distribution \(P\). This can also be regarded as a lossy compression setting for probability distributions. This paper describes encoding schemes for three cases of \(P\): \(P\) is a distribution over positive integers, \(P\) is a continuous distribution over \([0, 1]\) with a non-increasing pdf, and \(P\) is a continuous distribution over \([0, \infty)\) with a non-increasing pdf. We show that the growth rate of the expected codeword length is sub-linear in \(n\) when a power law bound is satisfied. An application of multiple-outputs channel simulation is the compression of probability distributions.

We study the multi-user Bayesian persuasion game between one encoder and two decoders, where the first decoder is better informed than the second decoder. We consider two perfect links, one to the first decoder only, and the other to both decoders. We consider that the encoder and both decoders are endowed with distinct and arbitrary distortion functions. We investigate the strategic source coding problem in which the encoder commits to an encoding while the decoders select the sequences of symbols that minimize their long-run respective distortion functions. We characterize the optimal encoder distortion value by considering successive refinement coding with respect to a specific probability distribution which involves two auxiliary random variables, and captures the incentive constraints of both decoders.

We study rate-distortion problems of a Poisson process using a group theoretic approach. By describing a realization of a Poisson point process with either point timings or inter-point intervals and by choosing appropriate distortion measures, we establish rate-distortion problems of a homogeneous Poisson process as ball- or sphere-covering problems for realizations of the hyperoctahedral group in .\Reals^n.. Specifically, the realizations we investigate are a hypercube and a hyperoctahedron. Thereby we unify three known rate-distortion problems of a Poisson process (with different distortion measures, but resulting in the same rate-distortion function) with the Laplacian-.\ell_1. rate-distortion problem.

The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed "partial clique-expansion" to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.

Side information improves the accuracy in community detection problems. While experimental results demonstrate the superior performance of many detection methods based on both the node attributes and graph structure, the question of the fundamental limit of the error rate for exact recovery remains open. In this paper, we obtain the asymptotic optimal error rate in the sense of exact recovery for a special two-community symmetric stochastic block model (SSBM) with side information consisting of multiple features. Our result provides insight on the number of features and nodes in the graph needed for community detection.

The role that side information plays in improving the exact recovery threshold in the stochastic block model (SBM) has been studied in many aspects. This paper studies exact recovery in n node balanced binary symmetric SBM with side information, given in the form of O(log n) i.i.d. samples at each node. A sharp exact recovery threshold is obtained and turns out to coincide with an existing threshold result, where no balanced constraint is imposed. Our main contribution is an efficient semi-definite programming (SDP) algorithm that achieves the optimal exact recovery threshold. Compared to the existing works on SDP algorithm for SBM with constant number of samples as side information, the challenge in this paper is to deal with the number of samples increasing in n.

In this paper, we consider the equivocation of finite blocklength coset codes when used over binary erasure wiretap channels. We make use of the equivocation matrix in comparing codes that are suitable for scenarios with noisy channels for both the intended receiver and an eavesdropper. Equivocation matrices have been studied in the past only for the binary erasure wiretap channel model with a noiseless channel for the intended recipient. In that case, an exact relationship between the elements of equivocation matrices for a code and its dual code was identified. The majority of work on coset codes for wiretap channels only addresses the noise-free main channel case, and extensions to noisy main channels require multi-edge type codes. In this paper, we supply a more insightful proof for the noiseless main channel case, and identify a new dual relationship that applies when two-edge type coset codes are used for the noisy main channel case. The end result is that the elements of the equivocation matrix for a dual code are known precisely from the equivocation matrix of the original code according to fixed reordering patterns. Such relationships allow one to study the equivocation of codes and their duals in tandem, which simplifies the search for best and/or good finite blocklength codes of various sizes. This paper is the first work that succinctly links the equivocation/error correction capabilities of dual codes for two-edge type coset coding over erasure-prone main channels.

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first examine the setup where the source at the input of an ISI-WTC is unconstrained and then, based on a general achievability result for arbitrary wiretap channels, we derive an achievable secure rate for this ISI-WTC. Afterwards, we examine the setup where the source at the input of an ISI-WTC is constrained to be a finite-state machine source (FSMS) of a certain order and structure. Optimizing the parameters of this FSMS toward maximizing the secure rate is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function by a suitable surrogate function whose maximum can be found efficiently.

This work studies the secrecy-capacity of a scalar-Gaussian wiretap channel with an amplitude constraint on the input. It is known that for this channel, the secrecy-capacity-achieving distribution is discrete with finitely many points. This work improves such result by showing an upper bound of the order ..\frac{A}{\sigma_1^2}.. where ..A.. is the amplitude constraint and ..\sigma_1^2.. is the variance of the Gaussian noise over the legitimate channel.

The well known Maddah-Ali-Niesen (MAN) coded caching scheme for users with dedicated cache is extended for use in multi-access coded cache scheme where the number of users need not be same as the number of caches in the system. The well known MAN scheme is recoverable as a special case of the multi-access system considered. The performance of this scheme is compared with the existing works on multi-access coded caching. To be able to compare the performance of different multi-access schemes with different number of users for the same number of caches, the terminology of per user rate (rate divided by the number of users) introduced in \cite{KNS} is used.

Recently multi-access coded caching schemes with number of users different from the number of caches obtained from a special case of resolvable designs called Cross Resolvable Designs (CRDs) have been reported and a new performance metric called rate-per-user has been introduced [8]. In this paper we present a generalization of this work resulting in multi-access coded caching schemes with improved rate-per-user.

The multi-access variant of the coded caching problem in the presence of an external wiretapper is investigated . A multi-access coded caching scheme with $K$ users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is proposed, which is secure against the wiretappers. Each transmission in the conventional insecure scheme will be now encrypted by a random key. The proposed scheme uses a novel technique for the key placement in the caches. It is also shown that the proposed secure multi-access coded caching scheme is within a constant multiplicative factor from the information-theoretic optimal rate for .L\geq \frac{K}{2}. and .N\geq 2K..

Data traffic in a client-server framework exhibits a temporal variability leading to congestion of resources at peak hours. One prevalent technique to overcome this problem is to load popular content/data into cache memories distributed across the end users. In this paper, the multi-access coded caching problem is considered in which each client is connected to multiple consecutive caches in a cyclic wrap around fashion and the cache memories are arbitrarily loaded in a decentralized manner. A new delivery scheme is proposed for the decentralized multi-access coded caching problem. A lower bound on the delivery rate is also obtained for the decentralized multi-access coded caching problem using techniques from index coding. The delivery scheme is shown to be optimal among all linear schemes when the number of caches associated with each user satisfies certain constraints.

The dual normal factor graph and the factor graph duality theorem have been considered for discrete graphical models. In this paper, we show an application of the factor graph duality theorem to continuous graphical models. Specifically, we propose a method to solve exactly the Gaussian graphical models defined on the ladder graph if certain conditions on the local covariance matrices are satisfied. Unlike the conventional approaches, the efficiency of the method depends on the position of the zeros in the local covariance matrices. The method and details of the dualization are illustrated on two toy examples.

Consider a pair of random vectors \( (\mathbf{X},\mathbf{Y}) \) and the conditional expectation operator \( \mathbb{E}[\mathbf{X}|\mathbf{Y}=\mathbf{y}] \). This work studies analytic properties of the conditional expectation by characterizing various derivative identities. The paper consists of two parts. In the first part of the paper, a general derivative identity for the conditional expectation is derived. Specifically, for the Markov chain \( \mathbf{U} \leftrightarrow \mathbf{X} \leftrightarrow \mathbf{Y} \), a compact expression for the Jacobian matrix of \( \mathbb{E}[\mathbf{U}|\mathbf{Y} = \mathbf{y}] \) is derived. In the second part of the paper, the main identity is specialized to the exponential family. Moreover, via various choices of the random vector \(\mathbf{U}\), the new identity is used to recover and generalize several known identities and derive some new ones. As a first example, a connection between the Jacobian of \(\mathbb{E}[\mathbf{X}|\mathbf{Y}=\mathbf{y}]\) and the conditional variance is established. As a second example, a recursive expression between higher order conditional expectations is found, which is shown to lead to a generalization of the Tweedy's identity. Finally, as a third example, it is shown that the \(k\)-th order derivative of the conditional expectation is proportional to the \((k+1)\)-th order conditional cumulant.

The existence of a unique Augustin mean and its invariance under the Augustin operator are established for arbitrary input distributions with finite Augustin information for channels with countably generated output σ-algebras. The existence is established by representing the conditional Rényi divergence as a lower semicontinuous and convex functional in an appropriately chosen uniformly convex space and then invoking the Banach-Saks property in conjunction with the lower semicontinuity and the convexity. A new family of operators is proposed to establish the invariance of the Augustin mean under the Augustin operator for orders greater than one. Some members of this new family strictly decrease the conditional Rényi divergence, when applied to the second argument of the divergence, unless the second argument is a fixed point of the Augustin operator.

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal inter-rack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

Modern distributed storage systems are increasingly implementing erasure codes to obtain better storage performance. In such systems, it is desirable to regenerate a failed storage node in a cost-effective manner since node failures occur frequently in real-world storage networks. Fractional repetition (FR) codes are a special class of regenerating codes that enable efficient recovery of failed storage nodes. In this paper, we introduce expandable FR codes, wherein both the number of storage nodes and the capacity of each node in the storage systems can be readily expanded. We present explicit constructions of expandable FR codes by applying two families of combinatorial structures called embeddable quasi-residual designs and extendible t-designs. Moreover, we study the property of constructed codes for some special scenarios.

We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size A_w slots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of A_b slots for Bob, where A_b < A_w. In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When A_w is increasing exponentially in n, we characterize the covert capacity as a function of A_w and A_b. When A_w is increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).

We consider the problem of covert sequential testing, in which a legitimate party attempts to run a sequential test while escaping detection from an adversary.Specifically, the legitimate party's decisions should meet prescribed risk constraints and, simultaneously, the adversary's observations induced by the test should remain indistinguishable from the observations obtained in the absence of a test. Our main result is the characterization of the risk exponentγθ, which captures the asymptotic exponential decrease of the risk with the square-root of the averaged stopping time in the limit of low risk.An example is provided to illustrate how the covertness constraint influences the design of the sequential test.

Based on the covert communication framework, we consider a covert queueing problem that has a Markovian statistic. Willie jobs arrive according to a Poisson process and require service from server Bob. Bob does not have a queue for jobs to wait and hence when the server is busy, arriving Willie jobs are lost. Willie and Bob enter a contract under which Bob should only serve Willie jobs. As part of the usage statistic, for a sequence of N consecutive jobs that arrived, Bob informs Willie whether each job was served or lost (this is the Markovian statistic). Bob is assumed to be violating the contract and admitting non-Willie (Nillie) jobs according to a Poisson process. For such a setting, we identify the hypothesis testing to be performed (given the Markovian data) by Willie to detect the presence or absence of Nillie jobs. We also characterize the upper bound on arrival rate of Nillie jobs such that the error in the hypothesis testing of Willie is arbitrarily large, ensuring covertness in admitting Nillie jobs.

In this paper, we consider the age of information (AoI) of a discrete time status updating system, focusing on finding the stationary AoI distribution assuming that the Ber/G/1/1 queue is used. Following the standard queueing theory, we show that by invoking a two-dimensional state vector which tracks the AoI and packet age in system simultaneously, the stationary AoI distribution can be derived by analyzing the steady state of the constituted two-dimensional stochastic process. We give the general formula of the AoI distribution and calculate the explicit expression when the service time is also geometrically distributed. The discrete and continuous AoI are compared, we depict the mean of discrete AoI and that of continuous time AoI for system with M/M/1/1 queue. Although the stationary AoI distribution of some continuous time single-server system has been determined before, in this paper, we shall prove that the standard queueing theory is still appliable to analyze the discrete AoI, which is even stronger than the proposed methods handling the continuous AoI.

We consider a multi-source status update system in which status updates are transmitted as packets containing the measured value of the monitored process and a time stamp representing the time when the sample was generated. The packets of each source are generated according to a Poisson process and served according to an exponentially distributed service time. We assume that the received status update packets need further processing before being used (hence, computation-intensive). This is mathematically modeled by an additional server at the sink. The sink server serves the packets according to an exponentially distributed service time. We introduce two packet management policies, a preemptive policy and a blocking policy, and derive the moment generating function (MGF) of the AoI of each source under the both policies. In the both policies, the system can contain at most two packets, one at the transmitter server and one at the sink server. In the preemptive policy, a new arriving packet preempts any possible packet that is currently under service regardless of the packet's source index. In the blocking policy, when a server is busy at the arrival instant of a packet, the arriving packet is blocked and cleared. We assume that the same preemptive/blocking policy is employed in both the transmitter and sink server. Numerical results are provided to assess the results.

We propose a simple model to study the tradeoff between timeliness and distortion, where different pieces of data have a different cost of not being sent. We pose the question of finding the optimal tradeoff as a policy design problem amenable to dynamic programming methods. We study the structural properties of optimal transmission policies, give an algorithmic procedure to find the optimal tradeoff, and numerically evaluate some instances.

In distributed machine learning (DML), the training data is distributed across multiple worker nodes to perform the underlying training in parallel. One major problem affecting the performance of DML algorithms is presence of stragglers. These are nodes that are terribly slow in performing their task which results in under-utilization of the training data that is stored in them. Towards this, gradient coding mitigates the impact of stragglers by adding sufficient redundancy in the data. Gradient coding and other straggler mitigation schemes assume that the straggler behavior of the worker nodes is identical. Our experiments on the Amazon AWS cluster however suggest otherwise and we see that there is a correlation in the straggler behavior across iterations. To model this, we introduce a heterogeneous straggler model where nodes are categorized into two classes, slow and active. To better utilize training data stored with slow nodes, we modify the existing gradient coding schemes with shuffling of the training data among workers. Our results (both simulation and cloud experiments) suggest remarkable improvement with shuffling over existing schemes. We perform theoretical analysis for the proposed models justifying their utility.

We introduce a class of codes, called Squeezed Random Khatri-Rao Product (RKRP) codes, for coded matrix multiplication when each worker node can perform multiple submatrix products. The proposed codes are a generalization of RKRP codes in [1] and are built on the idea of squeezed polynomial codes in [2]. We show that squeezed RKRP codes are maximum distance separable with probability 1. They have the same communication cost as that of squeezed polynomial codes while offering better numerical stability.

Coded distributed matrix multiplication (CDMM) schemes, such as MatDot codes, seek efficient ways to distribute matrix multiplication task(s) to a set of N distributed servers so that the answers returned from any R servers are sufficient to recover the desired product(s). For example, to compute the product of matrices U; V, MatDot codes partition each matrix into p > 1 sub-matrices to create smaller coded computation tasks that reduce the upload/storage at each server by 1/p, such that UV can be recovered from the answers returned by any R = 2p−1 servers. An important concern in CDMM is to reduce the recovery threshold R for a given storage/upload constraint. Recently, Jeong et al. introduced Approximate MatDot (AMD) codes that are shown to improve the recovery threshold by a factor of nearly 2, from 2p − 1 to p. A key observation that motivates our work is that the storage/upload required for approximate computing depends not only on the dimensions of the (coded) sub-matrices that are assigned to each server, but also on their precision levels - a critical aspect that is not explored by Jeong et al. Our main contribution is a dimensional analysis of AMD codes inspired by the Generalized Degrees of Freedom (GDoF) framework previously developed for wireless networks, which indicates that for the same upload/storage, once the precision levels of the task assignments are accounted for, AMD codes surprisingly fall short in all aspects of even the trivial replication scheme which assigns the full computation task to every server. The dimensional analysis is supported by simple numerical experiments.

In this article, we propose a new variational approach to learn private and/or fair representations. This approach is based on the Lagrangians of a new formulation of the privacy and fairness optimization problems that we propose. In this formulation, we aim to generate representations of the data that keep a prescribed level of the relevant information that is not shared by the private or sensitive data, while minimizing the remaining information they keep. The proposed approach (i) exhibits the similarities of the privacy and fairness problems, (ii) allows us to control the trade-off between utility and privacy or fairness through the Lagrange multiplier parameter, and (iii) can be comfortably incorporated to common representation learning algorithms such as the VAE, the beta-VAE, the VIB, or the nonlinear IB.

This paper considers the problem of single-server Individually-Private Information Retrieval (IPIR). In this problem, a user wants to retrieve \(D\) messages belonging to a dataset of \(K\) messages stored on a single server. Initially, the user knows \(M\) other messages belonging to the dataset as side information, where the identities of these \(M\) messages are unknown to the server. The goal is to minimize the total amount of information that the user must download from the server while keeping the identity of each of the \(D\) desired messages individually private, i.e., the identity of every individual message wanted by the user must be protected. The capacity of IPIR, which is defined as the supremum of all achievable download rates, was previously characterized for \(D=2, M=1\). However, the capacity was left open for all other values of \(D, M\). In this work, we present a technique for the proof of converse, based on a novel combinatorial approach. Using this technique, we establish an upper bound on the capacity of IPIR for \(D=2, M=2\). For this setting, we also propose a new IPIR scheme---based on a probabilistic partitioning of the messages, that achieves the capacity upper bound. We believe that our approach can be employed for proving the converse and designing optimal schemes for the general cases of the problem.

We consider the problem of publishing data with utility and privacy guarantees in a statistical decision-theoretical framework. In this framework, we introduce a statistical decision-theoretic quantity called average gain for measuring not only privacy but also utility. We also show a relationship between the average gain and the α-leakage, a tunable leakage measure proposed by Liao et al. Moreover, we formulate the privacy-utility trade-off (PUT) problem using Stratonovich's value of information (VoI) and present an analysis of the PUT.

In this paper, we consider sequential testing over a single-sensor, a single-decision center setup. At each time instant t, the sensor gets k samples (k>0) and describes the observed sequence until time t to the decision center over a zero-rate noiseless link. The decision center sends a single bit of feedback to the sensor to request for more samples for compression/testing or to stop the transmission. We have characterized the optimal exponent of type-II error probability under the constraint that type-I error probability does not exceed a given threshold \epsilon\in (0,1) and also when the expectation of the number of requests from decision center is smaller than n which tends to infinity. Interestingly, the optimal exponent coincides with that for fixed-length hypothesis testing with zero-rate communication constraints.

Cascaded binary hypothesis testing is studied in this paper with two decision centers at the relay and the receiver. All terminals have their own observations, where we assume that the observations at the transmitter, the relay, and the receiver form a Markov chain in this order. The communication occurs over two hops, from the transmitter to the relay and from the relay to the receiver. Expected rate constraints are imposed on both communication links. In this work, we characterize the optimal type-II error exponents at the two decision centers under constraints on the allowed type-I error probabilities. Our recent work characterized the optimal type-II error exponents in the special case when the two decision centers have same type-I error constraints and provided an achievability scheme for the general setup. To obtain the exact characterization for the general case, in this paper we provide a new converse proof as well as a new matching achievability scheme. Our results indicate that under unequal type-I error constraints at the relay and the receiver, a tradeoff arises between the maximum type-II error probabilities at these two terminals. Previous results showed that such a tradeoff does not exist under equal type-I error constraints or under general type-I error constraints when a maximum rate constraint is imposed on the communication links.

In this paper, we consider the distributed hypothesis testing (DHT) problem where two nodes are constrained to transmit constant bits to a central decoder. In such cases, we show that in order to achieve the optimal error exponents, it suffices to consider the empirical distributions of observed data sequences and encode them to the transmission bits. With such a coding strategy, we develop a geometric approach in the distribution spaces to show the optimal achievable error exponents and coding scheme for the following cases: (i) both nodes can transmit log 2 3 bits; (ii) one of the nodes can transmit 1 bit, and the other node is not constrained; (iii) the joint distribution of the nodes are conditionally independent given one hypothesis. Our approach essentially reveals new potentials for characterizing the precise error exponents for DHT with general communication constraints.

The problem of reconstruction of strings based upon their substrings spectrum has received significant attention recently due to its applicability to DNA applications in storage and sequencing. In contrast to previous works, we consider in this paper the setup of this problem where multiple strings are reconstructed together. Given a multiset S of strings, all their substrings of some fixed length \ell, defined as the \ell-profile of S, are received and the goal is to reconstruct all strings in the multiset S. A multi-strand \ell-reconstruction code is a set of multisets such that every multiset S can be reconstructed from its \ell-profile. Given the number of strings k and their length n, we first find a lower bound on the value of \ell to have multi-strand \ell-reconstruction codes with asymptotic rate 1. We then present two constructions of such codes and show that their rates approach 1 for values of \ell that asymptotically behave like the lower bound to have this asymptotic rate.

Synthetic DNA is an attractive alternative for data storage media due to its high information density, low energy usage, and exceptional robustness. Enzymatic DNA synthesis was recently introduced to allow cost effective synthesis of longer DNA molecules for data storage. This method is characterized by stutter errors which are sticky insertions so that every base in the designed sequence may be synthesized more than once. In this work, we study the problem of reconstructing the original sequence from a set of noisy reads originating from the stuttering enzymatic synthesis. We present different reconstruction algorithms and analyze their expected success probability and error rate for three different scenarios that depend on the information which is known about the stutter errors. We evaluate algorithmic performance analytically as well as by using simulations. We are especially interested in characterizing the performance as a function of the read depth. Our findings can be used to evaluate the trade-offs between synthesis quality indicators and the sequencing depth required for reconstruction with high probability. In principle, the probability of reconstruction failure exponentially decays with the sequencing depth, as demonstrated in the study. We also analyze the use of error-correcting codes to improve the error performance.

DNA is considered a promising alternative to traditional storage media because of advantages such as high data density, longevity, and ease of generating copies. One of the major drawbacks of DNA data storage however is that DNA synthesis is costly and resource intensive. A newly proposed enzymatic method has the potential to decrease the cost of synthesis but has the disadvantage that the number of times a base is repeated cannot be precisely controlled. The method is also prone to deletion of runs. Existing encoding approaches for this synthesis method either have a low rate, specifically, ..\le \log_2 3.. per run, or cannot protect against deletion errors. The current paper proposes a new error-correcting code and a synchronization algorithm that can combat deletions and achieve a code rate higher than ..\log_2 3.. bits per unit time.

The context tree source is a source model in which the occurrence probability of symbols is determined from a finite past sequence, and is a broader class of sources that includes i.i.d. and Markov sources. This paper proposes a source model such that its subsequence is generated from a different context tree model. The Bayes code for such sources requires weighting of the posterior probability distributions for the change patterns of the context tree source and all possible context tree models. Therefore, the challenge is how to reduce this exponential order computational complexity. In this paper, we assume a special class of prior probability distribution of change patterns and context tree models, and propose an efficient Bayes coding algorithm whose computational complexity is the polynomial order.

In this paper, we study the connection between entropic optimal transport and entropy power inequality (EPI). First, we prove an HWI-type inequality making use of the infinitesimal displacement convexity of optimal transport map. Second, we derive two Talagrand-type inequalities using the saturation of EPI that corresponds to a numerical term in our expression. We evaluate for a wide variety of distributions this term whereas for Gaussian and i.i.d. Cauchy distributions this term is found in explicit form. We show that our results extend previous results of Gaussian Talagrand inequality for Sinkhorn distance to the strongly log-concave case.

We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deciding whether the intersection of the entropic region and a given affine subspace is empty. This is a step towards the conjecture on the undecidability of conditional independence implication. The undecidability is proved via a reduction from the periodic tiling problem (a variant of the domino problem).

A finite-length random coding bound on the maximum-likelihood decoding error probability for an ensemble of irregular NB LDPC codes with QAM signaling for specific code symbol-to-signal mappings is derived. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized NB quasi-cyclic (QC)-LDPC codes used in various coded modulation schemes are presented. Comparison with the same performance of the optimized binary QC-LDPC block codes in the WiFi and 5G standards, as well as with the new bound is performed.

In this paper, we derive the exact input/output transfer functions of the optimal a-posteriori probability channel detector for a general ISI channel with erasures. Considering three channel impulse responses of different memory as an example, we compute the BP and MAP thresholds for regular spatially coupled LDPC codes with joint iterative detection and decoding. When we compare the results with the thresholds of ISI channels with Gaussian noise we observe an apparent inconsistency, i.e., a channel which performs better with erasures performs worse with AWGN. We show that this anomaly can be resolved by looking at the thresholds from an entropy perspective. We finally show that with spatial coupling we can achieve the symmetric information rates of different ISI channels using the same code.

A popular method of improving the throughput of blockchain systems is by running smaller side blockchains that push the hashes of their blocks onto a trusted blockchain. Side blockchains are vulnerable to stalling attacks where a side blockchain node pushes the hash of a block to the trusted blockchain but makes the block unavailable to other side blockchain nodes. Recently, Sheng et al. proposed a data availability oracle based on LDPC codes and a data dispersal protocol as a solution to the above problem. While showing improvements, the codes and dispersal protocol were designed disjointly which may not be optimal in terms of the communication cost associated with the oracle. In this paper, we provide a tailored dispersal protocol and specialized LDPC code construction based on the Progressive Edge Growth (PEG) algorithm, called the dispersal-efficient PEG (DE-PEG) algorithm, aimed to reduce the communication cost associated with the new dispersal protocol. Our new code construction reduces the communication cost and, additionally, is less restrictive in terms of system design.

In secret key agreement (SKA) in multiterminal channel model, terminals are connected by a noisy discrete memoryless channel (DMC) with multiple input and multiple outputs. Terminals can use the DMC to obtain correlated randomness, and communicate over a noiseless public channel to establish a shared secret key among a designated subset of terminals. We focus on a special class of multiterminal channel models, called wiretapped Polytree-PIN, in which the noisy channel consists of a set of independent point-to-point channels whose underlying undirected connectivity graph forms a tree. We consider a wiretap setting, where the output of each point-to-point channel is partially leaked to a passive wiretapper adversary, Eve, through a second independent noisy channel. A secure SKA protocol generates a group secret key such that Eve has no information about it. In this paper, we derive the wiretap secret key capacity, which is the largest achievable secret key rate, of the wiretapped Polytree-PIN model. Our result also implies the key capacity of the non-wiretapped Polytree-PIN model, that is the case when there is no leakage from point-to-point channels to Eve.

Digital fingerprinting codes are used to protect copyrighted contents from unauthorized redistribution. In this paper we focus on a digital fingerprinting code that can identify both of two malicious users and investigate coding theorems. We give a new definition of an identifier of the malicious users which enables us to give an explicit formula of the joint capacity, the supremum achievable rate of the number of users. Two coding theorems are given under the two kinds of setups depending on the knowledge of an attack model of the malicious users.

Most methods for publishing data with privacy guarantees introduce randomness into datasets which reduces the utility of the published data. In this paper, we study the privacy-utility tradeoff by taking maximal leakage as the privacy measure and the expected Hamming distortion as the utility measure. We study three different but related problems. First, we assume that the data-generating distribution (i.e., the prior) is known, and we find the optimal privacy mechanism that achieves the smallest distortion subject to a constraint on maximal leakage. Then, we assume that the prior belongs to some set of distributions, and we formulate a min-max problem for finding the smallest distortion achievable for the worst-case prior in the set, subject to a maximal leakage constraint. Lastly, we define a partial order on privacy mechanisms based on the largest distortion they generate. Our results show that when the prior distribution is known, the optimal privacy mechanism fully discloses symbols with the largest prior probabilities, and suppresses symbols with the smallest prior probabilities. Furthermore, we show that sets of priors that contain more uniform distributions lead to larger distortion, while privacy mechanisms that distribute the privacy budget more uniformly over the symbols create smaller worst-case distortion.

The expected excess risk of a learning algorithm is the average suboptimality of using the learning algorithm, relative to the optimal hypothesis in the hypothesis class. In this work, we lower bound the expected excess risk of a learning algorithm using the mutual information between the input and the noisy output of the learning algorithm. The setting we consider is, where the hypothesis class is the set of real numbers and the true risk function has a local strong convexity property. Our main results also lead to asymptotic lower bounds on the expected excess risk, which do not require the knowledge of the local strong convexity constants of the true risk function.

Generalization error captures the degree to which the output of a learning algorithm overfits the training data. We obtain a family of bounds which generalize the bounds developed by Xu & Raginsky (2017) and Bu, Zou and Veeravalli (2019), under certain assumptions. Our bounds are based on the Rényi analogue of the Donsker-Varadhan representation of Kullback-Leibler divergence. We also obtain bounds on the probability of generalization error which recover the bounds of Esposito, Gastpar and Issa (2020). We also give a multiplicative lower bound on the expected true loss for a 0-1 loss function.

This paper studies the statistical characterization of detecting an adversary who wants to harm some computation such as machine learning models or aggregation by altering the output of a differentially private mechanism in addition to discovering some information about the underlying dataset. An adversary who is able to modify the published information from a differentially private mechanism aims to maximize the possible damage to the system while remaining undetected. We present a trade-off between the privacy parameter of the system, the sensitivity and the attacker's advantage (the bias) through determining the threshold for the best critical region of the hypothesis testing problem for deciding whether or not the adversary's attack is detected. Such trade-offs are provided for Laplace mechanisms using one-sided and two-sided hypothesis tests. Corresponding error probabilities are analytically derived and ROC curves are presented for various levels of the sensitivity, the absolute mean of the attack and the privacy parameter. Subsequently, we provide an interval for the bias induced by the adversary so that the defender detects the attack. Finally, we adapt the Kullback-Leibler differential privacy to adversarial classification.

A novel SISO decoding algorithm for linear block codes is presented. This algorithm is based on the recursive trellises and performs two passes over the recursion tree. Probability-domain implementation and its LogMax approximation are considered. Numeric results show that proposed method has lower complexity compared to the other known recursive algorithms and the classical BCJR algorithm.

A complexity-adaptive tree search algorithm is proposed for ..\boldsymbol{G}_N..-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to ..N=128... By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified ..\boldsymbol{G}_N..-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.

This paper proposes a low-complexity decoding algorithm for complex low-density lattice codes (CLDLC). The key is a method to approximate an infinite complex Gaussian mixture that occurs at the variable node of the belief propagation (BP) decoder. We define the reliability of check-to-variable messages and a threshold function to determine the number of complex Gaussian functions to use in the approximation. This allows the number of Gaussians in the approximation to be adaptively selected depending upon its reliability. By using the minimum number of Gaussians needed for an accurate approximation, the complexity of the decoder can be significantly reduced. The reliability is based on a likelihood function, and we form an upper bound on the Kullback-Leibler (KL) divergence to find the threshold function via linear regression. The approximation based on reliability of each message can reduce the complexity to O(n · t · 1.35 d−1 ) at high volume-to-noise ratio (VNR), where n is the lattice dimension, d is the degree of the inverse generator matrix, and t is the number of iterations. This algorithm provides higher performance and lower complexity compared to previously proposed approximation algorithms. and provides higher performance and lower complexity compared to previously proposed approximation algorithms.

We study the information leakage to a guessing adversary in index coding with a general message distribution. Under both vanishing-error and zero-error decoding assumptions, we develop lower and upper bounds on the optimal leakage rate, which are based on the broadcast rate of the subproblem induced by the set of messages the adversary tries to guess. When the messages are independent and uniformly distributed, the lower and upper bounds match, establishing an equivalence between the two rates.

In this work, we study the secure index coding problem where there are security constraints on both legitimate receivers and eavesdroppers. We develop two performance bounds (i.e., converse results) on the symmetric secure capacity. The first one is an extended version of the basic acyclic chain bound (Liu and Sadeghi, 2019) that takes security constraints into account. The second converse result is a novel information-theoretic lower bound on the symmetric secure capacity, which is interesting as all the existing converse results in the literature for secure index coding give upper bounds on the capacity.

We study the problem of identification over a DMC wiretap channel under effective secrecy. In identification, due to the fact that single messages are compared to each other, all conditions are inherently semantic, and thus we are forced to consider semantic effective secrecy. We show that even considering effective secrecy "comes for free" by giving an achievability theorem for stealth identification. We use two concatenated transmission codes, the first one is a resolvability transmission code. The second code is an effective-secrecy transmission code. An achievable rate is derived for the problem.

This paper proposes a general framework to design a sparse sensing matrix A\in R^{m\times n}, in a linear measurement system y = \Ax^{\natural} + w, where y \in R^n, x^{\natural}\in R^n, and w denote the measurements, the signal with certain structures, and the measurement noise, respectively. By viewing the signal reconstruction from the measurements as a message passing algorithm over a graphical model, we leverage tools from coding theory in the design of low density parity check codes, namely the density evolution, and provide a framework for the design of matrix A. Particularly, compared to the previous methods, our proposed framework enjoys the following desirable properties: (i) Universality: the design supports both regular reconstruction and preferential reconstruction, and incorporates them in a single framework; (ii) Flexibility: the framework can easily adapt the design of A to a signal x^{\natural} with different underlying structures. As an illustration, we consider the L1 regularizer, which correspond to Lasso, for both the regular reconstruction and preferential reconstruction scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., m\geq c_0 k\log(n/k) (the regular reconstruction) with regular design after proper distribution approximation, where c_0 > 0 is some fixed constant. We also provide numerical experiments to confirm the analytical results and demonstrate the superiority of our framework whenever a preferential treatment of a sub-block of vector x^{\natural} is required.

In 1-bit compressive sensing, each measurement is quantized to a single bit, namely the sign of a linear function of an unknown vector, and the goal is to accurately recover the vector. While it is most popular to assume a standard Gaussian sensing matrix for 1-bit compressive sensing, using structured sensing matrices such as partial Gaussian circulant matrices is of significant practical importance due to their faster matrix operations. In this paper, we provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing with partial Gaussian circulant matrices (with random column sign flips) under a generative prior, where the signal to estimate is assumed to belong to the range of a Lipschitz continuous generative model with bounded inputs. Under suitable assumptions, we match guarantees that were previously only known to hold for i.i.d.~Gaussian matrices requiring significantly more computation.

Periodic signals admit sparse representations in nested periodic dictionaries (NPDs). While sparse recovery algorithms rooted in the theory of compressive sensing can successfully recover their underlying periods, existing recovery conditions derived for random dictionaries are of limited use in this context as they fail to explain the achievability results of said algorithms. In addition, provable achievability guarantees specific to NPDs have been heretofore lacking. In this paper, we derive exact recovery conditions for sparse periodic signals by leveraging prior information about the structure of NPDs. As instances of such dictionaries, we investigate the achievability conditions for the Farey and the Ramanujan Periodicity Transform dictionaries. Our numerical results demonstrate that the newly derived conditions can provide guarantees for exact recovery with the Farey dictionary, and in turn for exact period estimation, for large enough data lengths.

Recently, it was found that clipping can significantly improve the section error rate (SER) performance of sparse regression (SR) codes if an optimal clipping threshold is chosen. In this paper, we propose irregularly clipped SR codes, where multiple clipping thresholds are applied to symbols according to a distribution, to further improve the SER performance of SR codes. Orthogonal approximate message passing (OAMP) algorithm is used for decoding. Using state evolution, the distribution of irregular clipping thresholds is optimized to minimize the SER of OAMP decoding. As a result, optimized irregularly clipped SR codes achieve a better tradeoff between clipping distortion and noise distortion than regularly clipped SR codes. Numerical results demonstrate that irregularly clipped SR codes achieve 0.4 dB gain in signal-to-noise-ratio (SNR) over regularly clipped SR codes at code length 2.5 x 10^4 and SER = 10^-5. We further show that irregularly clipped SR codes are robust over a wide range of code rates.

STAR codes are well-known binary Maximum Distance Separable (MDS) array codes with triple fault tolerance and low encoding/decoding complexity, yet the update complexity of STAR codes is sub-optimal. We propose STAR+ codes, which extend STAR codes to achieve asymptotically optimal update complexity. We show that STAR+ codes are the generalized version of STAR codes with triple fault tolerance, and additionally have strictly less complexity in encoding, decoding, and updates than STAR codes for most parameters.

We construct linear codes over odd prime fields for correcting two-dimensional (2-D) Lee-errors on the hexagonal signal constellations. They are obtained by puncturing and enlarging either RS codes or BCH codes. We introduce 2-D Lee-weight on the hexagonal constellations in the same way as the method presented by the first author in ISIT'19, and propose an effective method for correcting Lee-errors of weight greater than or equal to 1. The concept of value-locator of an error, which was introduced implicitly by K. Nakamura in the late 1970s and early 1980s and inherited to the ISIT'19 paper, is a key for decoding Lee-error-correcting codes. Our method is based on the Buchberger algorithm for finding Gröbner bases of ideals in the multivariate polynomial ring. A result of simulations shows that our method works well for correcting Lee-errors of small weight.

We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality \(q^{n-d+1}\) is far from having minimum distance \(d\), i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

A conditional version of Sibson's α-information is defined using a simple closed-form "log-expectation" expression, which satisfies important properties such as consistency, uniform expansion, and data processing inequalities. This definition is compared to previous ones, which in contrast do not satisfy all of these properties. Based on our proposal and on a generalized Fano inequality, we extend the case α=1 of previous works to obtain sharp universal upper bounds for the probability of success of any type side-channel attack, particularly when α = 2.

A secret-sharing scheme is $d$-multiplicative if it allows the players to multiply $d$ (rather than two) shared secrets (without recovering them) by {\em locally} converting their shares into an additive sharing of the product. In this work, the $d$-multiplicative secret-sharing (MSS) scheme is extended to a hybrid MSS (HMSS), which is mainly designed for $d$ secrets shared against different access structures. A necessary and sufficient condition for $n$-player $d$-HMSS schemes to exist is presented. The sufficiency is constructively proven based on the replication-based secret-sharing scheme. The necessity for any general case is reduced to the impossibility of a minimum case. The results holds for arbitrary (possibly inefficient or even nonlinear) secret-sharing schemes.

We study the problem of rate-distortion-equivocation with side-information only available at the decoder when an independent private random key is shared between the sender and the receiver. The sender compresses the sequence, and the receiver reconstructs it such that the average distortion between the source and the output is limited. The equivocation is measured at an eavesdropper that intercepts the source encoded message, utilizing side-information correlated with the source and the side-information at the decoder. We have derived the entire achievable rate-distortion-equivocation region for this problem.

This paper studies the intersections of insertion and deletion balls. The t-insertion, t-deletion ball of a sequence x is the set of all sequences received by t insertions, deletions to x, respectively. While the intersection of either deletion balls or insertion balls has been rigorously studied before, the intersection of an insertion ball and a deletion ball has not been addressed so far. We find the maximum intersection size of any two insertion and deletion balls in the binary case. For the special case of one-insertion and one-deletion balls we find the intersection size for all pair of sequences. Then, we derive the largest and average values of this intersection size. Lastly, we present an algorithm that efficiently computes the intersection of any t1-insertion ball and t2-deletion ball.

We study properties of binary runlength-limited sequences with additional constraints on their weight and/or the number of runs of identical symbols they contain. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for the run-preserving insertion-deletion channel, a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences.

We use linear programming (LP) to derive upper and lower bounds on the ``kissing number'' Ad of any q-ary linear code C with distance distribution frequencies A_i, in terms of the given parameters [n, k, d]. In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient as the kissing number is low.

We investigate the problem of common randomness (CR) generation from discrete correlated sources aided by one-way communication over single-user multiple-input multiple-output (MIMO) slow fading channels with additive white Gaussian noise (AWGN), arbitrary state distribution and with channel state information available at the receiver side (CSIR). We completely solve the problem by first characterizing the channel outage capacity of MIMO slow fading channels for arbitrary state distribution. For this purpose, we also provide an achievable rate for a specific compound MIMO Gaussian channel. Second, we define the outage CR capacity of the MIMO slow fading channel and establish a single-letter characterization of it using our result on its outage transmission capacity.

Information transmission over a multiple-input-multiple-output (MIMO) fading channel with imperfect channel state information (CSI) is investigated, under a new receiver architecture which combines the recently proposed generalized nearest neighbor decoding rule (GNNDR) and a successive procedure in the spirit of successive interference cancellation (SIC). Recognizing that the channel input-output relationship is a nonlinear mapping under imperfect CSI, the GNNDR is capable of extracting the information embedded in the joint observation of channel output and imperfect CSI more efficiently than the conventional linear scheme, as revealed by our achievable rate analysis via generalized mutual information (GMI). Numerical results indicate that the proposed scheme achieves performance close to the channel capacity with perfect CSI, and significantly outperforms the conventional pilot-assisted scheme, which first estimates the CSI and then uses the estimated CSI as the true one for coherent decoding.

In a multiple-input multiple-output (MIMO) broadcast channel (BC), the difference in spatial transmit correlation matrices of different users is called transmit correlation diversity. Recently, several works have extended this concept beyond its original scope, to include channels whose transmit correlation matrices have non-overlapping eigenspaces. In contrast to earlier analyses of overlapping eigenspaces that were mostly described in terms of degrees-of-freedom, this work presents achievable rate regions. These achievable regions are derived by rate-splitting, product superposition, or a combination thereof. Our rate expressions make explicit the contribution of the common parts and individual (non-overlapping) parts of the correlation eigenspaces toward the achievable rate region. As a by-product, a result of Hassibi and Hochwald on MIMO channel training is extended to channels with spatial correlation.

We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. In this setting, samples of an unknown state are requested sequentially and a decision to either continue or to accept one of the two hypotheses is made after each test. Under the constraint that the number of samples is bounded, either in expectation or with high probability, we exhibit adaptive strategies that minimize both types of misidentification errors. Namely, we show that these errors decrease exponentially (in the stopping time) with decay rates given by the measured relative entropies between the two states. Moreover, if we allow joint measurements on multiple samples, the rates are increased to the respective quantum relative entropies. We also fully characterize the achievable error exponents for non-adaptive strategies and provide numerical evidence showing that adaptive measurements are necessary to achieve our bounds.

We provide the first inner bounds for sending private classical information over a quantum multiple access channel. We do so by using three powerful information theoretic techniques: rate splitting, quantum simultaneous decoding for multiple access channels, and a novel smoothed distributed covering lemma for classical quantum channels. Our inner bounds are given in the one shot setting and accordingly the three techniques used are all very recent ones specifically designed to work in this setting. The last technique is new to this work and is our main technical advancement. For the asymptotic iid setting, our one shot inner bounds lead to the natural quantum analogue of the best classical inner bounds for this problem.

Quantum state transfer involves two parties who use pre-shared entanglement and noiseless communication in order to transfer parts of a quantum state. In this work, we quantify the communication cost of one-shot state splitting in terms of the partially smoothed max-information. We then give an analysis of state splitting in the moderate deviation regime, where the error in the protocol goes sub-exponentially fast to zero as a function of the number of i.i.d. copies. The main technical tool we derive is a tight relation between the partially smoothed max-information and the hypothesis testing relative entropy, which allows us to obtain the expansion of the partially smoothed max-information for i.i.d. states in the moderate deviation regime. This then also establishes the moderate deviation analysis for other variants of state transfer such as state merging and source coding.

This work considers a Poisson noise channel with an amplitude constraint. It is well-known that the capacity-achieving input distribution for this channel is discrete with finitely many points. We sharpen this result by introducing upper and lower bounds on the number of mass points. In particular, the upper bound of order ..A \log^2(A).. and lower bound of order ..\sqrt{A}.. are established where ..A.. is the constraint on the input amplitude. In addition, along the way, we show several other properties of the capacity and capacity-achieving distribution. For example, it is shown that the capacity is equal to .. - \log P_{Y^\star}(0).. where ..P_{Y^\star}.. is the optimal output distribution. Moreover, an upper bound on the values of the probability masses of the capacity-achieving distribution and a lower bound on the probability of the largest mass point are established.

This paper investigates the problem of synthesizing joint distributions in the finite-length regime. For a fixed block-length n and an upper bound on the distribution approximation epsilon, we prove a capacity result for fixed-length strong coordination. It is shown analytically that the rate conditions for the fixed-length regime are lower-bounded by the mutual information that appears in the asymptotical condition plus Q^-1 (epsilon) sqrt(V/n), where V is the channel dispersion, and Q^-1 is the inverse of the Gaussian cumulative distribution function.

We generalize the problem of controlling the interference created to an external observer while communicating over a Discrete Memoryless Channel (DMC) which was studied in [1]. In particular, we consider the scenario where the transmission is established over a compound DMC channel with unknown state at both the encoder and the decoder. Depending on the exact state s of the channel, we ask for a different level of average precision Δs on the establishment of the interference coordination with the external observer. For this set-up, we fully characterize the capacity region.

In this paper, the fundamental limits on the rates at which information and energy can be simultaneously transmitted over an additive white Gaussian noise channel are studied under the following assumptions: (a) the channel is memoryless; (b) the number of channel input symbols (constellation size) and block length are finite; and (c) the decoding error probability (DEP) and the energy outage probability (EOP) are bounded away from zero. In particular, it is shown that the limits on the maximum information and energy transmission rates; and the minimum DEP and EOP, are essentially set by the type induced by the code used to perform the transmission. That is, the empirical frequency with which each channel input symbol appears in the codewords. Using this observation, guidelines for optimal constellation design for simultaneous energy and information transmission are presented.

In this paper, we study the fundamental limits of simultaneous information and power transfer over a Rayleigh fading channel in the presence of high-power amplifier (HPA) nonlinearity. In particular, a three-party communication system is considered, where a transmitter aims simultaneously conveying information to an information receiver and delivering energy to an energy harvester receiver. We study the information-energy capacity region and the associated input distribution under: i) average-power, peak-power (PP) constraints at the transmitter, b) HPA nonlinearity at the transmitter, and c) nonlinearity of the energy harvesting circuit at the energy receiver. By extending Smith's mathematical framework, we show that the optimal input distribution under those constraints is discrete with a finite number of mass points. Moreover, we derive a closed-form expression of the capacity-achieving distribution for the low PP regime, where there is no trade-off between information and energy transfer. Finally, we show that HPA significantly reduces the information energy capacity region.

We study the problem of transmitting a source sample with minimum distortion over an infinite-bandwidth additive white Gaussian noise channel under an energy constraint. To that end, we construct a joint source-channel coding scheme using analog pulse position modulation (PPM) and bound its quadratic distortion. We show that this scheme outperforms existing techniques since its quadratic distortion attains both the exponential and polynomial decay orders of Burnashev's outer bound.

In this paper, a problem of joint source-channel coding for computing functions of outputs from correlated sources is studied. In particular, the system of computing two-input functions where one of two outputs is available at the decoder as full-side information is investigated. Our result reveals that if the sensitivity of functions introduced by Ahlswede and Csisz\'ar and the smoothness of sources introduced by Kuzuoka and Watanabe are satisfied, then the condition that the function is computable over the channel (i.e., the value of the function is correctly decoded) coincides with that for the identity function (i.e., reproducing the entire source outputs).

Secret-sharing building blocks based on quantum broadcast communication are studied. The confidential capacity region of the pure-loss bosonic broadcast channel is determined with key assistance, under the assumption of the long-standing minimum output-entropy conjecture. If the main receiver has a transmissivity of ..\eta<\frac{1}{2}.., then confidentiality solely relies on the key-assisted encryption of the one-time pad. We also address conference key agreement for the distillation of two keys, a public key and a secret key. A regularized formula is derived for the key-agreement capacity region. In the pure-loss bosonic case, the key-agreement region is included within the capacity region of the corresponding broadcast channel with confidential messages. We then consider a network with layered secrecy, where three users with different security ranks communicate over the same broadcast network. We derive an achievable layered-secrecy region for a pure-loss bosonic channel that is formed by the concatenation of two beam splitters.

The distillable entanglement of a bipartite quantum state does not exceed its entanglement cost. This well known inequality can be understood as a second law of entanglement dynamics in the asymptotic regime of entanglement manipulation, excluding the possibility of perpetual entanglement extraction machines that generate boundless entanglement from a finite reserve. In this paper, I establish a refined second law of entanglement dynamics that holds for the non-asymptotic regime of entanglement manipulation.

Semi-source independent quantum random number generators (SI-QRNG) are cryptographic protocols which attempt to extract random strings from quantum sources where the source is under the control of an adversary (but with known dimension) while the measurement devices are fully characterized. This represents a middle-ground between fully-trusted and full-device independence, allowing for fast bit-generation rates with current-day technology, while also providing a strong security guarantee. In this paper we analyze a SI-QRNG protocol based on quantum walks and develop a proof of security. We derive a novel entropic uncertainty relation for this application which is necessary since standard relations actually fail in this case.

This paper considers an additive Gaussian noise channel with arbitrarily distributed finite variance input signals. It studies the differential entropy of the minimum mean-square error (MMSE) estimator and provides a new lower bound which connects the differential entropy of the input, output, and conditional mean. That is, the sum of differential entropies of the conditional mean and output is always greater than or equal to twice the input differential entropy. Various other properties such as upper bounds, asymptotics, Taylor series expansion, and connection to Fisher Information are obtained. An application of the lower bound in the remote-source coding problem is discussed, and extensions of the lower and upper bounds to the vector Gaussian channel are given.

In this work, we study commitment over a class of channels called reverse elastic channels (RECs). In the commitment problem, two mutually distrustful parties, say Alice and Bob, seek to commit on a bit string available to Alice. The parties interact via a commitment protocol comprising two phases, viz., commit phase followed by reveal phase. Alice commits to a string, and transmits it to Bob securely in a manner Bob cannot learn it until Alice chooses to reveal it; at the time of reveal, however, Bob can successfully detect if Alice cheats. It is well known that noisy channels are a promising resource to realize information-theoretically secure commitment; however, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees. Particularly problematic is a scenario where dishonest parties can actively alter the channel characteristics. RECs are an interesting class of such unreliable channels, where essentially only a dishonest committer Alice can meaningfully alter the channel; RECs have attracted active recent interest. Our principal contribution is the REC commitment capacity characterization for all parameters; this proves a recent related conjecture. Apart from presenting an achievable scheme, a key result in our work is a tight converse which analyses a specific cheating strategy by Alice. The significance of RECs stems from the fact that along with elastic channels (ECs), where only a dishonest receiver Bob can alter the channel, these two channel models represent special cases of the more widely studied unfair noisy channels (UNCs). Interestingly, for a given set of parameters, our result shows that the REC commitment capacity is no larger than that for the ECs. Furthermore, similar to the ECs, RECs offer non-trivial commitment throughput for all meaningful parameters; this is in stark contrast to UNCs where the throughput may possibly be zero.

Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede's characterization of the zero-error-capacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

Wireless relay network is a solution for transmitting information from a source node to a sink node far away by installing a relay in between. The broadcasting nature of wireless communication allows the sink node to receive part of the data sent by the source node. In this way, the relay does not need to receive the whole piece of data from the source node and it does not need to forward everything it received. In this paper, we consider the application of batched network coding, a practical form of random linear network coding, for a better utilization of such a network. The amount of innovative information at the relay which is not yet received by the sink node, called the innovative rank, plays a crucial role in various applications including the design of the transmission scheme and the analysis of the throughput. We present a visualization of the innovative rank which allows us to understand and derive formulae related to the innovative rank with ease.

We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design interactive coding schemes that successfully perform any computation over these noisy networks and strive to reduce their communication overhead with respect to the original (noiseless) computation. A simple variant of a coding scheme by Rajagopalan and Schulman (STOC 1994) shows that any (noiseless) protocol of ..R.. rounds can be reliably simulated in ..O(R\log n).. rounds over a network with ..n=n_1n_2+1.. parties in which a single party is connected to ..n_2.. noisy broadcast channels, each of which connects ..n_1.. distinct parties. We design new coding schemes with improved overheads. Our approach divides the network into four regimes according to the relationship between ..n_1.. and ..n_2... We employ a two-layer coding where the inner code protects each broadcast channel and is tailored to the specific conditions of the regime in consideration. The outer layer protects the computation in the network and is generally based on the scheme of Rajagopalan and Schulman, adapted to the case of broadcast channels. The overhead we obtain ranges from ..O(\log\log n_2).. to ..O(\log n_2 \frac{\log\log n_1}{\log n_1}).. and beats the trivial ..O(\log n).. overhead in all four regimes.

We study the problem of calibrating a quantum receiver for optical coherent states when transmitted on a quantum optical channel with variable transmissivity, a common model for long-distance optical-fiber and free/deep-space optical communication. We optimize the error probability of legacy receivers, such as Kennedy's and Dolinar's, on average with respect to the channel transmissivity distribution. We then compare our results with the ultimate error probability attainable by a general quantum device, computing the Helstrom bound for mixtures of coherent-state hypotheses, for the first time to our knowledge, and with homodyne measurements. Then, we employ a recently introduced library of shallow reinforcement learning methods, demonstrating that the receiver can be calibrated under practical conditions in real time, based only on training samples of the signals transmitted through the variable channel.

In this paper, we prove the equivalence of inserting separable quantum states and deletions. Hence any quantum code that corrects deletions automatically corrects separable insertions. First, we describe the quantum insertion/deletion error using the Kraus operators. Next, we develop an algebra for commuting Kraus operators corresponding to insertions and deletions. Using this algebra, we prove the equivalence between quantum insertion codes and quantum deletion codes using the Knill-Laflamme conditions.

In this paper we derive closed-form formulas of feedback capacity and nonfeedback achievable rates, for Additive Gaussian Noise (AGN) channels, driven by unstable i.e., nonstationary, autoregressive moving average (ARMA) noise (with one unstable pole and one unstable zero), based on channel inputs generated by optimal, two-parameter time-invariant feedback strategies or induced channel input distributions. From the analysis and simulations follows the surprising observations, (i) the use of time-invariant channel input distributions gives rise to multiple regimes of capacity that depend on the parameters of the ARMA noise, which may or may not use feedback, (ii) for an autoregressive noise, the higher the unstable pole the higher the capacity, (iii) for a moving average noise, the higher the unstable zero the higher the capacity, (iv) for the ARMA noise, as the pole and zero get closer together the capacity decreases.

The multiple-input multiple output (MIMO) generalization of Cover's and Pombra's Gaussian feedback capacity is considered. An equivalent sequential characterization of the finite block or transmission feedback information (FTFI) capacity is derived, with the optimal channel input processes expressed as functional of a sufficient statistic and a Gaussian orthogonal innovations process. From the new representations follows that the Cover and Pombra characterization of the FTFI capacity is expressed as a functional of two generalized matrix difference Riccati equations (DRE) of filtering theory of Gaussian systems. The new characterization, although, more complex than existing formulas that appeared in the literature, its sequential optimization formulation offers computational advantages, especially for MIMO channels.