Search

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$. In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node. [ABSTRACT FROM AUTHOR]

This paper formulates a distributed computation problem, where a master asks ${\mathsf N}$ distributed workers to compute a linearly separable function. The task function can be expressed as ${\mathsf K}_{\mathrm{ c}}$ linear combinations of ${\mathsf K}$ messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any ${\mathsf N}_{\mathrm{ r}}$ out of ${\mathsf N}$ workers the master can recover the task function with high probability, where the coefficients of the ${\mathsf K}_{\mathrm{ c}}$ linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used ‘cyclic assignment’ scheme on the datasets. Our results also show that when ${\mathsf K}= {\mathsf N}$ , with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandon et al. from which the master recovers one linear combination of ${\mathsf K}$ messages, our proposed scheme can let the master recover any additional ${\mathsf N}_{\mathrm{ r}}-1$ independent linear combinations of messages with high probability. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [ABSTRACT FROM AUTHOR]

This paper studies a memoryless state-dependent multiple access channel (MAC) where two transmitters wish to convey a message to a receiver under the assumption of causal and imperfect channel state information at transmitters (CSIT) and imperfect channel state information at receiver (CSIR). In order to emphasize the limitation of transmitter cooperation between physically distributed nodes, we focus on the so-called distributed CSIT assumption, i.e., where each transmitter has its individual channel knowledge, while the message can be assumed to be partially or entirely shared a priori between transmitters by exploiting some on-board memory. Under this setup, the first part of the paper characterizes the common message capacity of the channel at hand for arbitrary CSIT and CSIR structure. The optimal scheme builds on Shannon strategies, i.e., optimal codes are constructed by letting the channel inputs be a function of current CSIT only. For a special case when CSIT is a deterministic function of CSIR, the considered scheme also achieves the capacity region of a common message and two private messages. The second part addresses an important instance of the previous general result in a context of a cooperative multi-antenna Gaussian channel under i.i.d. fading operating in frequency-division duplex mode, such that CSIT is acquired via an explicit feedback of perfect CSIR. The capacity of the channel at hand is achieved by distributed linear precoding applied to Gaussian codes. Surprisingly, we demonstrate that it is suboptimal to send a number of data streams bounded by the number of transmit antennas as typically considered in a centralized CSIT setup. Finally, numerical examples are provided to evaluate the sum capacity of the binary MAC with binary states as well as the Gaussian MAC with i.i.d. fading. [ABSTRACT FROM AUTHOR]

In this paper, we consider a status updating system where updates are generated at a constant rate at $K$ sources and sent to the corresponding recipients through a noise-free broadcast channel. We assume that perfect channel state information (CSI) is available at the transmitter before each transmission, and the transmitter is able to utilize the CSI to precode the updates. Our object is to design optimal precoding schemes to minimize the summed average age of information (AoI) at the recipients. Under various assumptions on the size of each update $B$ , the number of transmit antennas $M$ , and the number of receive antennas $N$ at each user, this paper identifies the corresponding age-optimal precoding and transmission scheduling strategies. Specifically, for the case when $N=1$ , a round-robin based updating scheme is shown to be optimal. For the two-user systems with $N>B$ or $M\notin [N:2N]$ , framed updating schemes are proven to be optimal. For other cases in the two-user systems, a framed alternating updating scheme is proven to be 2-optimal. [ABSTRACT FROM AUTHOR]

This paper derives the optimal test channel distribution and the complete characterization of the classical Gorbunov and Pinsker (1973), Gorbunov and Pinsker (1974) nonanticipatory epsilon entropy of multivariate Gaussian Markov sources with square-error fidelity, which remained an open problem since 1974. The paper also formulates a state dependent nonanticipatory epsilon entropy, in which past reproductions are available to the decoder and not to the encoder, the test channel is specified with respect to an auxiliary (state) random process, and the reproduction process is a causal function of past reproduction and the auxiliary random process. This variation is analogous to the Wyner and Ziv (1976) and Wyner (1978) rate distortion function (RDF), of memoryless sources. It is shown that the operational rate of zero-delay codes, with past reproductions available to the decoder but not to the encoder is bounded below by the state dependent nonanticipatory epsilon entropy rate. For the case of multivariate Gaussian Markov sources with square-error fidelity, the optimal test channel distribution and the complete characterization of the state dependent of nonanticipatory epsilon entropy are derived, and also shown that that the two nonanticipatory epsilon entropies coincide. The derivations are new; they are based on structural properties of the stochastic realizations of the reproduction process that induce the optimal test channel distributions. They are derived using, achievable lower bounds on information theoretic measures, properties of mean-square estimation theory, Hadamard’s inequality, and canonical correlation coefficients of a tuple of multivariate jointly Gaussian random processes. Applications of the nonanticipatory epsilon entropy and its state dependent variation are discussed to the areas of control of unstable Gaussian systems over limited memory channels, design of causal estimators for Gaussian Markov sources with a fidelity criterion, computation of the rate loss of causal and zero-delay codes of Gaussian Markov sources with respect to non-causal codes. [ABSTRACT FROM AUTHOR]

Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal channel side information (CSI) available at the encoder, and also when CSI is not available. This model can be viewed as a form of quantum metrology, and as the quantum counterpart of the classical rate-and-state channel with state estimation at the decoder. Regularized formulas for the capacity-distortion regions are derived. In the special case of measurement channels, single-letter characterizations are derived for the strictly-causal and causal settings. Furthermore, in the more general case of entanglement-breaking channels, a single-letter characterization is derived when CSI is not available. As a consequence, we obtain regularized formulas for the capacity of random-parameter quantum channels with CSI, generalizing previous results by Boche et al., 2016, on classical-quantum channels. Bosonic dirty paper coding is introduced as a consequence, where we demonstrate that the optimal coefficient is not necessarily that of minimum mean-square error estimation as in the classical setting. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence ${x}$ of length $n$. Bob wishes to guess ${x}$ , yet he is satisfied with finding any sequence $\hat {x}$ which is within a given distortion $D$ from $x$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the guesswork), and analyzing its properties (e.g., its $\rho $ –th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically–secured systems, where the “password” which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some ${x}$ , and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario. [ABSTRACT FROM AUTHOR]

This paper investigates the secret-key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Over multiple rounds of communication, the adversary first decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the goal of the adversary being to have the decoder accept and decode their observation as a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret-key-authenticated-capacity region here is then defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the first of a two-part study, with the parts differing in their measure of the authentication rate. In this first study, the authentication rate is the exponent of blocklength-normalized exponent of the expected probability of false authentication. For this metric, we provide an inner bound which improves on those existing in the literature. This is achieved by adopting and merging different classical techniques in novel ways. Within these classical secret-key-based authentication techniques, one technique derives authentication capability from secure channel coding to send the secret key with the message, and the other technique derives its authentication capability directly from obscuring the source. [ABSTRACT FROM AUTHOR]

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works. [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

In blind compression of quantum states, a sender Alice is given a specimen of a quantum state $\rho $ drawn from a known ensemble (but without knowing what $\rho $ is), and she transmits sufficient quantum data to a receiver Bob so that he can decode a near perfect specimen of $\rho $. For many such states drawn iid from the ensemble, the asymptotically achievable rate is the number of qubits required to be transmitted per state. The Holevo information is a lower bound for the achievable rate, and is attained for pure state ensembles, or in the related scenario of entanglement-assisted visible compression of mixed states wherein Alice knows what state is drawn. In this paper, we prove a general and robust lower bound on the achievable rate for ensembles of classical states, which holds even in the least demanding setting when Alice and Bob share free entanglement and a constant per-copy error is allowed. We apply the bound to a specific ensemble of only two states and prove a near-maximal separation (saturating the dimension bound in leading order) between the best achievable rate and the Holevo information for constant error. This also implies that the ensemble is incompressible – compression does not reduce the communication cost by much. Since the states are classical, the observed incompressibility is not fundamentally quantum mechanical. We lower bound the difference between the achievable rate and the Holevo information in terms of quantitative limitations to clone the specimen or to distinguish the two classical states. [ABSTRACT FROM AUTHOR]

This paper considers the transmission of an infinite sequence of messages (a streaming source) over a packet erasure channel, where every source message must be recovered perfectly at the destination subject to a fixed decoding delay. While the capacity of a channel that introduces only bursts of erasures has been known for more than fifteen years, only recently, the capacity of a channel with either one burst of erasures or multiple arbitrary erasures in any fixed-sized sliding window has been established. However, explicit codes shown to achieve this capacity for any admissible set of parameters require a large field size that scales exponentially with the delay. Recently, it has been shown that there exist codes that achieve the capacity with field size which scales quadratically with the delay. However, explicit constructions were shown only to specific combinations of parameters. This work describes an explicit rate-optimal construction for all admissible channel and delay parameters over a field size that scales quadratically with the delay. [ABSTRACT FROM AUTHOR]

Blowfish privacy is a recent generalisation of differential privacy that enables improved utility while maintaining privacy policies with semantic guarantees, a factor that has driven the popularity of differential privacy in computer science. This paper relates Blowfish privacy to an important measure of privacy loss of information channels from the communications theory community: min-entropy leakage. Symmetry in an input data neighbouring relation is central to known connections between differential privacy and min-entropy leakage. But while differential privacy exhibits strong symmetry, Blowfish neighbouring relations correspond to arbitrary simple graphs owing to the framework’s flexible privacy policies. To bound the min-entropy leakage of Blowfish-private mechanisms we organise our analysis over symmetrical partitions corresponding to orbits of graph automorphism groups. A construction meeting our bound with asymptotic equality demonstrates tightness. [ABSTRACT FROM AUTHOR]

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter. [ABSTRACT FROM AUTHOR]

In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number $n$ of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as $n$ increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is the binary relative entropy $D\left({\frac {1}{2}\|\max (p,q)}\right)$ , where $p$ and $q$ are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihel et al., 2019]. In addition, we show that the computation time required by the teacher and student is linear in $n$. We also study a more general setting in which the binary symmetric channels are replaced by general binary-input discrete memoryless channels. We provide an achievability bound and a converse bound, and show that the two coincide in certain cases, including (i) when the two channels are identical, and (ii) when the student-teacher channel is a binary symmetric channel. More generally, we give sufficient conditions under which our learning rate is the best possible for block-structured protocols. [ABSTRACT FROM AUTHOR]

It is well known that the capacity region of an average transmit power constrained Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers is enlarged by the presence of causal noiseless feedback. When the noise variances at the receivers are identical, even passive feedback via independent memoryless Gaussian links can lead to a capacity region enlargement. The last fact remains true even when the feedback noise variance is very high, and available only from one of the receivers. While such capacity enlargements are feasible for several other feedback models in the Gaussian BC setting, it is also known that feedback does not change the capacity region for physically degraded broadcast channels. In this paper, we consider a two user GBC with independent noise realizations at the receivers, where the feedback links from the receivers are corrupted by independent additive Gaussian noise processes. We investigate the set of four noise variances, two forward and two feedback, for which no capacity enlargement is possible. A sharp characterization of this region is derived, i.e., any quadruple outside the presented region will lead to a capacity enlargement, whereas quadruples inside will leave the capacity region unchanged. Our results lead to the conclusion that when the forward noise variances are different, too noisy a feedback from one of the receivers alone is not always beneficial for enlarging the capacity region, be it from the stronger user or the weaker one, in sharp contrast to the case of equal forward noise variances. [ABSTRACT FROM AUTHOR]

We consider the use of the well-known dual capacity bounding technique for deriving upper bounds on the capacity of indecomposable finite-state channels (FSCs) with finite input and output alphabets. In this technique, capacity upper bounds are obtained by choosing suitable test distributions on the sequence of channel outputs. We propose test distributions that arise from certain graphical structures called Q-graphs. As we show in this paper, the advantage of this choice of test distribution is that, for the important sub-classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as a dynamic programming (DP) problem, which makes the bounds tractable. We illustrate this for several examples of FSCs, where we are able to solve the associated DP problems explicitly to obtain capacity upper bounds that either match or beat the best previously reported bounds. For instance, for the classical trapdoor channel, we improve the best known upper bound of 0.661 (due to Lutz (2014)) to 0.584, shrinking the gap to the best known lower bound of 0.572, all bounds being in units of bits per channel use. [ABSTRACT FROM AUTHOR]

We derive universal classical-quantum superposition coding and universal classical-quantum multiple access channel coding by using generalized packing lemmas for the type method. Using our classical-quantum universal superposition code, we establish the capacity region of a classical-quantum compound broadcast channel with degraded message sets. Our universal classical-quantum multiple access channel codes have two types of codes. One is a code with joint decoding and the other is a code with separate decoding. It is not so easy to construct a former code that universally achieves general points of the capacity region beyond corner points. First, we construct the latter code that universally achieves general points of the capacity region. Then, converting the latter code to the former coder, we construct the above desired code with the former type. [ABSTRACT FROM AUTHOR]

We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε > 0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ = 2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2 × 2 kernel) on the BEC is μ = 3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ × ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ (ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ (ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(n log n). [ABSTRACT FROM AUTHOR]

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). Hence, one can construct examples of the aforementioned problems that are independent of ZFC (assuming ZFC is consistent). [ABSTRACT FROM AUTHOR]

We study the problem of simulating a two-user multiple-access channel (MAC) over a multiple access network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links between each encoder and the decoder, and there is independent pairwise shared randomness between all the three possible pairs of nodes. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the two sources and the side information. We are interested in the rate tuples which permit this simulation. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). When the pairwise shared randomness between the encoders is absent, the setting reduces to a special case of MAC simulation using another MAC studied by Haddadpour et al. (2013). We establish that the presence of encoder shared randomness can strictly improve the communication rate requirements. We first show that the inner bound derived from Haddadpour et al. (2013) is tight when the sources at the encoders are conditionally independent given the side-information at the decoder. This result recovers the existing results on point-to-point channel simulation and function computation over such multi-terminal networks. We then explicitly compute the communication rate regions for an example both with and without the encoder shared randomness and demonstrate that its presence strictly reduces the communication rates. Inner and outer bounds for the general case are also obtained. [ABSTRACT FROM AUTHOR]

It is well known that independent (separate) encoding of $K$ correlated sources may incur some rate loss compared to joint encoding, even if the decoding is done jointly. This loss is particularly evident in the multiple descriptions problem, where it is the same source that is encoded in each description. We observe that under mild conditions about the source and distortion measure, the sum-rate of $K$ separately encoded individually good descriptions tends to the rate-distortion function of the joint decoder in the limit of vanishing small coding rates of the descriptions. Moreover, we then propose to successively encode the source into $K$ independent descriptions in each round in order to achieve a final distortion $D$ after $M$ rounds. We provide two examples – a Gaussian source with mean-squared error and an exponential source with one-sided error – for which the excess rate vanishes in the limit as the number of rounds $M$ goes to infinity, for any fixed $D$ and $K$. This result has an interesting interpretation for a multi-round variant of the multiple descriptions problem, where after each round the encoder gets a (block) feedback regarding which of the descriptions arrived: In the limit as the number of rounds $M$ goes to infinity (i.e., many incremental rounds), the total rate of received descriptions approaches the rate-distortion function. We provide theoretical and experimental evidence showing that this phenomenon is in fact more general than in the two examples above. [ABSTRACT FROM AUTHOR]

We define a new family of codes for symmetric classical-quantum channels and establish their optimality. To this end, we extend the classical notion of generalized perfect and quasi-perfect codes to channels defined over some finite dimensional complex Hilbert output space. The resulting optimality conditions depend on the channel considered and on an auxiliary state defined on the output space of the channel. For certain $N$ -qubit classical-quantum channels, we show that codes based on a generalization of Bell states are quasi-perfect and, therefore, they feature the smallest error probability among all codes of the same blocklength and cardinality. [ABSTRACT FROM AUTHOR]

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log (n)$ bits in one sub-regime, and at most $\Omega ({n})$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping. [ABSTRACT FROM AUTHOR]

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_\infty $ norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi et al. (ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures. [ABSTRACT FROM AUTHOR]

Aligned-Images Sum-set Inequalities are used in this work to study the Generalized Degrees of Freedom (GDoF) of the symmetric layered multi-hop interference channel under the robust assumption that the channel state information at the transmitters (CSIT) is limited to finite precision. First, the sum-GDoF value is characterized for the $2\times 2\times 2$ setting that is comprised of 2 sources, 2 relays, and 2 destinations. It is shown that the sum-GDoF does not improve even if perfect CSIT is allowed in the first hop, as long as the CSIT in the second hop is limited to finite precision. The sum GDoF characterization is then generalized to the $2\times 2\times \cdots \times 2$ setting that is comprised of $L$ hops. Remarkably, for large $L$ , the sum-GDoF value approaches that of the one-hop broadcast channel that is obtained by full cooperation among the two transmitters of the last hop, with finite precision CSIT. Previous studies of multi-hop interference networks either identified sophisticated GDoF optimal schemes under perfect CSIT, such as aligned interference neutralization and network diagonalization, that are powerful in theory but too fragile to be practical, or studied robust achievable schemes like classical amplify/decode/compress-and-forward without claims of information-theoretic optimality. In contrast, under finite precision CSIT, we show that the benefits of fragile schemes are lost, while a combination of classical random coding schemes that are simpler and much more robust, namely a rate-splitting between decode-and-forward and amplify-and-forward, is shown to be GDoF optimal. As such, this work represents another step towards bridging the gap between theory (optimality) and practice (robustness) with the aid of Aligned-Images Sum-set Inequalities. [ABSTRACT FROM AUTHOR]

Interactive coding allows two or more parties to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work (the second part) we provide computationally efficient, constant rate schemes that conduct any computation on arbitrary networks, and succeed with high probability in the presence of adversarial noise that can insert, delete, or alter communicated messages. Our schemes are non-fully-utilized and incur a polynomial (in the size of the network) blowup in the round complexity. Our first scheme resists an oblivious adversary that corrupts at most a fraction $\frac { \varepsilon }{m}$ of the total communication, where $m$ is the number of links in the network and $\varepsilon $ is a small constant. In contrast to the first part of this work, the scheme in this part does not assume that the parties pre-share a long random string. Our second scheme resists an arbitrary (non-oblivious) adversary that corrupts at most a fraction $\frac { \varepsilon }{m\log m}$ of the communication. We further improve the resilience to $\vphantom {\sum ^{R}}\frac { \varepsilon }{m\log \log m}$ by assuming the parties pre-share a long common random $\vphantom {\sum ^{R}}$ string. [ABSTRACT FROM AUTHOR]

Motivated by applications to DNA storage, we study reconstruction and list-reconstruction schemes for integer vectors that suffer from limited-magnitude errors. We characterize the asymptotic size of the intersection of error balls in relation to the code’s minimum distance. We also devise efficient reconstruction algorithms for various limited-magnitude error parameter ranges. We then extend these algorithms to the list-reconstruction scheme, and show the trade-off between the asymptotic list size and the number of required channel outputs. These results apply to all codes, without any assumptions on the code structure. Finally, we also study linear reconstruction codes with small intersection, as well as show a connection to list-reconstruction codes for the tandem-duplication channel. [ABSTRACT FROM AUTHOR]

We show that the problem of code construction for multiple access channel (MAC) resolvability can be reduced to the simpler problem of code construction for source resolvability. Specifically, we propose a MAC resolvability code construction that relies on a combination of multiple source resolvability codes, used in a black-box manner, and leverages randomness recycling implemented via distributed hashing and block-Markov coding. Since explicit source resolvability codes are known, our results also yield the first explicit coding schemes that achieve the entire MAC resolvability region for any discrete memoryless multiple-access channel with binary input alphabets. [ABSTRACT FROM AUTHOR]

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate—that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error—is $O(1/\sqrt {n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede’s wringing technique. The $O(1/\sqrt {n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt {n})$ term, although for most channels they do not match existing achievable bounds. [ABSTRACT FROM AUTHOR]

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error. [ABSTRACT FROM AUTHOR]

This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter $p$ (${\mathrm {BDC}}_{p}$) every bit is deleted independently with probability $p$. A lower bound of $(1-p)/9$ is known on the capacity of the ${\mathrm {BDC}}_{p}$ , yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate $(1-p)/16$ , for every $p$. This improves upon the work of Guruswami and Li (2018) that gave a construction of rate $(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter $\lambda $ (PRC $_{\lambda }$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean $\lambda $. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC $_{\lambda }$. [ABSTRACT FROM AUTHOR]

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$ , binary linear codes of block length $O(1/\delta ^{2+\alpha })$ and rate $I(W)-\delta $ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length $O(1/\delta ^{2})$. This quadratic dependence on the gap $\delta $ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity. [ABSTRACT FROM AUTHOR]

We introduce a new analysis technique to derive a single-letter upper bound on the mismatch capacity of a stationary, single-user, memoryless channel with a decoding metric $q$. Our bound is obtained by considering a multicast transmission over a two-user broadcast channel with decoding metrics $q$ and $\rho $ at the receivers, referred to as $(q,\rho)$ -surely degraded. This channel has the property that the intersection event of correct $q$ -decoding of receiver 1 and erroneous $\rho $ -decoding of receiver 2 has zero probability for any fixed-composition codebook of a certain composition $P$. Our bound holds in the strong converse sense of an exponential decay of the probability of correct decoding at rates above the bound. Further, we refine the proof and present a bound that is tighter than that of any choice of $\rho $. Several examples that demonstrate the strict improvement of our bound compared to previous results are analyzed. Finally, we detect equivalence classes of isomorphic channel-metric pairs $(W,q)$ that share the same mismatch capacity. We prove that if the class contains a matched pair, then our bound is tight and the mismatch capacity of the entire class is fully characterized and is equal to the LM rate, which is achievable by random coding, and may be strictly lower that the matched capacity. [ABSTRACT FROM AUTHOR]

We consider the most general finite-dimensional quantum mechanical information source, which is given by a quantum system $A$ that is correlated with a reference system $R$. The task is to compress $A$ in such a way as to reproduce the joint source state $\rho ^{AR}$ at the decoder with asymptotically high fidelity. This includes Schumacher’s original quantum source coding problem of a pure state ensemble and that of a single pure entangled state, as well as general mixed state ensembles. Here, we determine the optimal compression rate (in qubits per source system) in terms of the Koashi-Imoto decomposition of the source into a classical, a quantum, and a redundant part. The same decomposition yields the optimal rate in the presence of unlimited entanglement between compressor and decoder, and indeed the full region of feasible qubit-ebit rate pairs. [ABSTRACT FROM AUTHOR]

Optimal zero-delay coding (quantization) of $\mathbb {R}^{d}$ -valued linearly generated Markov sources is studied under quadratic distortion. The structure and existence of deterministic and stationary coding policies that are optimal for the infinite horizon average cost (distortion) problem are established. Prior results studying the optimality of zero-delay codes for Markov sources for infinite horizons either considered finite alphabet sources or, for the $\mathbb {R}^{d}$ -valued case, only showed the existence of deterministic and non-stationary Markov coding policies or those which are randomized. In addition to existence results, for finite blocklength (horizon) $T$ the performance of an optimal coding policy is shown to approach the infinite time horizon optimum at a rate $O\left({\frac {1}{T}}\right)$. This gives an explicit rate of convergence that quantifies the near-optimality of finite window (finite-memory) codes among all optimal zero-delay codes. [ABSTRACT FROM AUTHOR]

We study the following semi–deterministic setting of the joint source–channel coding problem: a deterministic source sequence (a.k.a. individual sequence) is transmitted via a memoryless channel, using delay-limited encoder and decoder, which are both implementable by periodically–varying finite-state machines, and the decoder is granted with access to side information, which is a noisy version of the source sequence. We first derive a lower bound on the achievable expected distortion in terms of the empirical statistics of the source sequence, the number of states of the encoder, the number of states of the decoder, their period, and the overall delay. The bound is shown to be asymptotically achievable by universal block codes in the limit of long blocks. We also derive a lower bound to the best achievable excess–distortion probability and discuss situations where it is achievable. Here, of course, source coding and channel coding cannot be completely separated without loss of optimality. Finally, we outline a few extensions of the model considered, such as: (i) incorporating a common reconstruction constraint, (ii) availability of side information at both ends, and (iii) extension to the Shannon channel with causal state information at the encoder. This work both extends and improves on earlier work of the same flavor (Ziv 1980, Merhav 2014), which focused only on the expected distortion, without side information at either end, and without the above mentioned additional ingredients. [ABSTRACT FROM AUTHOR]

This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term the conditional smooth-⋆ entropy. The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria. [ABSTRACT FROM AUTHOR]

We consider the problem of (almost) lossless separate encodings and joint decoding of two correlated discrete memoryless sources (DMSs), that is, the well-known Slepian-Wolf (S-W) source coding problem. Traditionally, ensembles of S–W codes are defined such that every bin of each $n$ –vector of each source is randomly drawn under the uniform distribution across the sets $\{0,1,\ldots,2^{nR_{X}}-1\}$ and $\{0,1,\ldots,2^{nR_{Y}}-1\}$ , where $R_{X}$ and $R_{Y}$ are the coding rates of the two sources, $X$ and $Y$ , respectively. In a few more recent works, where only one source, say, $X$ , is compressed and the other one, $Y$ , serves as side information available at the decoder, the scope is extended to variable–rate S–W (VRSW) codes, where the rate is allowed to depend on the type class of the source string, but still, the random–binning distribution is assumed uniform within the corresponding, type–dependent, bin index set. In this expository work, we investigate the role of the uniformity of the random binning distribution from the perspective of the trade-off between the reliability (defined in terms of the error exponent) and the compression performance (measured from the viewpoint of the source coding exponent). To this end, we study a much wider class of random–binning distributions, which includes the ensemble of VRSW codes as a special case, but it also goes considerably beyond. We first show that, with the exception of some pathological cases, the smaller ensemble, of VRSW codes, is as good as the larger ensemble in terms the trade-off between the error exponent and the source coding exponent. Notwithstanding this finding, the wider class of ensembles proposed is motivated in two ways. The first is that it outperforms VRSW codes in the above–mentioned pathological cases, and the second is that it allows robustness: in the event of a system failure that causes unavailability of the compressed bit–stream from one of the sources, it still allows reconstruction of the other source within some controllable distortion. [ABSTRACT FROM AUTHOR]

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

A minimax converse for the identification via channels is derived. By this converse, a general formula for the identification capacity, which coincides with the transmission capacity, is proved without the assumption of the strong converse property. Furthermore, the optimal second-order coding rate of the identification via channels is characterized when the type I error probability is non-vanishing and the type II error probability is vanishing. Our converse is built upon the so-called partial channel resolvability approach; however, the minimax argument enables us to circumvent a flaw reported in the literature. [ABSTRACT FROM AUTHOR]

Let $\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\}$ and let $n(m,q,\ell)$ be the smallest $n$ for which there is a code $C \subseteq \mathcal {X} ^{n}$ of $m$ elements such that for every list $w_{1}, w_{2}, \ldots, w_{\ell +1}$ of distinct codewords from $C$ , there is a coordinate $j \in [n]$ such that $\{w_{1}[j], w_{2}[j], \ldots, w_{\ell +1}[j]\} = \mathcal {X}$. We show that there is a constant $A>0$ such that for $\epsilon < 1/5$ , for all large $q$ and large enough $m$ ($m>q^{5}$), we have $n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m}$. This bound has consequences for the zero-error list-decoding capacity of the $q/(q-1)$ channel studied by Elias (1988). Our result implies that for $A$ and $\epsilon $ as above, the zero-error list-decoding capacity of the $q/(q-1)$ channel with list-size $\epsilon q\ln {q}$ is at most $\exp (-Aq^{1-5\epsilon })$ , that is, it falls exponentially as $q$ increases. This confirms a conjecture of Chakraborty et al. (2006). [ABSTRACT FROM AUTHOR]

Novel bounds on the left- and right-tail probability of the Binomial distribution are presented. Specifically, bounds on the left-tail probability $\text {P}\!\left [{S_{n}\leqslant an}\right]$ with $a\in (0,p)$ and the right-tail probability $\text {P}\!\left [{S_{n}\geqslant an}\right]$ with $a\in (p,1)$ , where $S_{n}$ follows the Binomial law with parameters $n\geqslant 1$ and $p\in (0,1)$ , are derived. The bounds are tighter than the best known closed-form expressions. The presented upper and lower bounds on the right-tail match an asymptotic expansion of $\log \text {P}\!\left [{S_{n}\geqslant na}\right]$ up to, and including, the $\log n$ term. In particular, the ratio between the upper and lower bounds is $1/(1-c/n)$ , where $c$ is independent of $n$. Similar results are presented for the left-tail probability. Applications to finite blocklength source and channel coding are presented. [ABSTRACT FROM AUTHOR]

We present a new systematic approach to constructing spherical codes in dimensions $2^{k}$ , based on Hopf foliations. Using the fact that a sphere $S^{2n-1}$ is foliated by manifolds $S_{\cos \eta }^{n-1} \times S_{\sin \eta }^{n-1}$ , $\eta \in [0,\pi /2]$ , we distribute points in dimension $2^{k}$ via a recursive algorithm from a basic construction in $\mathbb {R}^{4}$. Our procedure outperforms some current constructive methods in several small-distance regimes and constitutes a compromise between achieving a large number of codewords for a minimum given distance and effective constructiveness with low encoding computational cost. Bounds for the asymptotic density are derived and compared with other constructions. The encoding process has storage complexity $O(n)$ and time complexity $O(n \log n)$. We also propose a sub-optimal decoding procedure, which does not require storing the codebook and has time complexity $O(n \log n)$. [ABSTRACT FROM AUTHOR]

An $n$ -dimensional source with memory is observed by $K$ isolated encoders via parallel channels, who compress their observations to transmit to the decoder via noiseless rate-constrained links while leveraging their memory of the past. At each time instant, the decoder receives $K$ new codewords from the observers, combines them with the past received codewords, and produces a minimum-distortion estimate of the latest block of $n$ source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining the memory of the past. We extend the Berger-Tung inner and outer bounds to the scenario with inter-block memory, showing that the minimum asymptotically (as $n \to \infty $) achievable sum rate required to achieve a target distortion is bounded by minimal directed mutual information problems. For the Gauss-Markov source observed via $K$ parallel AWGN channels, we show that the inner bound is tight and solve the corresponding minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels. The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers. [ABSTRACT FROM AUTHOR]