Search

The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C ⊆ F2n has error-correcting capability e, we write t = e + ℓ, (ℓ ≥ 1). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound ℓ + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound ℓ + 1 is the best possible. Most of our other new results rely on constant weight codes. [ABSTRACT FROM AUTHOR]

Mutually orthogonal complementary sets (MOCSs) have received significant research attention in recent years due to their wide applications in communications and radar. Existing MOCSs which are constructed based on generalized Boolean functions (GBFs) mostly have lengths of power-of-two. How to construct MOCSs with non-power-of-two lengths whilst having large set sizes is a largely open problem. With the aid of GBFs, in this paper, we present new constructions of such MOCSs and show that the maximal achievable set size is 1/2 of the flock size of an MOCS. [ABSTRACT FROM AUTHOR]

The study of feedback has been mostly limited to single-hop communication settings. In this paper, we consider Gaussian networks where sources and destinations can communicate with the help of intermediate relays over multiple hops. We assume that links in the network can be bidirected providing opportunities for feedback. We ask the following question: can the information transfer in both directions of a link be critical to maximizing the end-to-end communication rates in the network? Equivalently, could one of the directions in each bidirected link (and more generally at least one of the links forming a cycle) be shut down and the capacity of the network still be approximately maintained? We show that in any arbitrary Gaussian network with bidirected edges and cycles and unicast traffic, we can always identify a directed acyclic subnetwork that approximately maintains the capacity of the original network. For Gaussian networks with multiple-access and broadcast traffic, an acyclic subnetwork is sufficient to achieve every rate point in the capacity region of the original network, however, there may not be a single acyclic subnetwork that maintains the whole capacity region. For networks with multicast and multiple unicast traffic, on the other hand, bidirected information flow across certain links can be critically needed to maximize the end-to-end capacity region. These results can be regarded as generalizations of the conclusions regarding the usefulness of feedback in various single-hop Gaussian settings and can provide opportunities for simplifying operation in Gaussian multihop networks. [ABSTRACT FROM PUBLISHER]

This paper considers the corner points of the capacity region of a two-user Gaussian interference channel (GIC). In a two-user GIC, the rate pairs where one user transmits its data at the single-user capacity (without interference), and the other at the largest rate for which reliable communication is still possible are called corner points. This paper relies on existing outer bounds on the capacity region of a two-user GIC that are used to derive informative bounds on the corner points of the capacity region. The new bounds refer to a weak two-user GIC (i.e., when both crosslink gains in standard form are positive and below 1), and a refinement of these bounds is obtained for the case where the transmission rate of one user is within \varepsilon > 0 of the single-user capacity. The bounds on the corner points are asymptotically tight as the transmitted powers tend to infinity, and they are also useful for the case of moderate SNR and INR. Upper and lower bounds on the gap (denoted by \Delta ) between the sum-rate and the maximal achievable total rate at the two corner points are derived. This is followed by an asymptotic analysis analogous to the study of the generalized degrees of freedom [where the SNR and INR scalings are coupled such that (\log (\text INR)/\log (\text SNR)) = \alpha \geq 0 ], leading to an asymptotic characterization of this gap which is exact for the whole range of \alpha . The upper and lower bounds on $\Delta $ are asymptotically tight in the sense that they achieve the exact asymptotic characterization. Improved bounds on $\Delta $ are derived for finite SNR and INR, and their improved tightness is exemplified numerically. [ABSTRACT FROM PUBLISHER]

We consider the problem of noisy Bayesian active learning where we are given a finite set of functions \mathcal H , a sample space \mathcal X , and a label set \mathcal L . One of the functions in \mathcal H assigns labels to samples in \mathcal X . The goal is to identify the function that generates the labels even though the result of a label query on a sample is corrupted by independent noise. More precisely, the objective is to declare one of the functions in \mathcal H as the true label generating function with high confidence using as a few label queries as possible, by selecting the queries adaptively and in a strategic manner. Previous work in Bayesian active learning considers generalized binary search and its variants for the noisy case, and analyzes the number of queries required by these sampling strategies. In this paper, we show that these schemes are, in general, suboptimal. Instead we propose and analyze an alternative strategy for sample collection. Our sampling strategy is motivated by a connection between Bayesian active learning and active hypothesis testing, and is based on querying the label of a sample, which maximizes the extrinsic Jensen–Shannon divergence at each step. We provide upper and lower bounds on the performance of this sampling strategy, and show that these bounds are better than the previous bounds in the literature. [ABSTRACT FROM PUBLISHER]

In the context of fix-free codes, the most important and immediate consequence of the 3/4-conjecture (if it is proven), is that the redundancy of an optimal binary fix-free code never exceeds 1 bit, as with the optimal prefix-free codes, i.e. Huffman codes. In this paper, this bound on the redundancy is proven without requiring the conjecture to be true. To do so, we use two known sufficient conditions for the existence of binary fix-free codes to derive an improved upper bound on the redundancy of an optimal fix-free code in terms of the largest symbol probability. [ABSTRACT FROM AUTHOR]

This paper studies the achievable degrees of freedom (DoF) for multi-user multiple-input multiple-output (MIMO) two-way relay channels, where there are K source nodes, each equipped with M antennas, one relay node, equipped with N antennas, and each source node exchanges independent messages with an arbitrary set of other source nodes via the relay. By allowing an arbitrary information exchange pattern, the considered channel model is a unified one. It includes several existing channel models as special cases: 1) K -user MIMO Y channel; 2) multi-pair MIMO two-way relay channel; 3) generalized MIMO two-way X relay channel; and 4) L -cluster MIMO multiway relay channel. Previous studies mainly considered the achievability of the DoF cut-set bound 2N at the antenna configuration N<2M for the K -user MIMO Y channel; 2) \frac NM \in \big (0, 2+\frac 4K\big ] \cup \big [K-2, +\infty \big) for the multi-pair MIMO two-way relay channel; and 3) \frac NM \in \big (0, 2+\frac 8K^2\big ] \cup \big [K-2, +\infty \big) for the generalized MIMO two-way X relay channel. We also provide the antenna configuration regions for the general multi-user MIMO two-way relay channel to achieve the total DoF $KM$ . [ABSTRACT FROM AUTHOR]

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound (or slightly weaker ones) is the assignment of weights to the hypergraph’s vertices in a way that they satisfy the constraints in the linear programming problem. In order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases significantly reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the $Z$ channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the nonbinary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion channel, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for single-deletion-correcting codes. Since the deletion and grain-error channels have a similar structure for a single error, we also improve upon the existing upper bounds on single-grain error-correcting codes. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case. [ABSTRACT FROM AUTHOR]

This paper studies adaptive sensing for estimating the nonzero amplitudes of a sparse signal with the aim of providing analytical guarantees on the performance gain due to adaptive resource allocation. We consider a previously proposed optimal two-stage policy for allocating sensing resources. For positive powers $q$ , we derive tight upper bounds on the mean $q$ th-power error resulting from the optimal two-stage policy and corresponding lower bounds on the improvement over nonadaptive uniform sensing. It is shown that the adaptation gain is related to the detectability of nonzero signal components as characterized by Chernoff coefficients, thus quantifying analytically the dependence on the sparsity level of the signal, the signal-to-noise ratio (SNR), and the sensing resource budget. For fixed sparsity levels and increasing SNR or sensing budget, we obtain the rate of convergence to oracle performance and the rate at which the fraction of resources spent on the first exploratory stage decreases to zero. For a vanishing fraction of nonzero components, the gain increases without bound as a function of SNR and sensing budget. Numerical simulations demonstrate that the bounds on adaptation gain are quite tight in nonasymptotic regimes as well. [ABSTRACT FROM AUTHOR]

The problem of detecting a single anomalous process among a finite number $M$ of processes is considered. At each time, a subset of the processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. The objective is a sequential search strategy that minimizes the expected detection time subject to an error probability constraint. This problem can be considered as a special case of active hypothesis testing first considered by Chernoff where a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically (as the error probability approaches zero) optimal. For the special case considered in this paper, we show that a simple deterministic test achieves asymptotic optimality and offers better performance in the finite regime. We further extend the problem to the case where multiple anomalous processes are present. In particular, we examine the case where only an upper bound on the number of anomalous processes is known. [ABSTRACT FROM PUBLISHER]

The Haroutunian exponent arises in the study of channel reliability functions for both block coding with feedback and fixed-delay coding without feedback. For asymmetric channels, such as the $Z$ -channel, the Haroutunian exponent is strictly larger than the sphere-packing exponent. The sphere-packing exponent is believed to be an upper bound for the reliability function in the two aforementioned communication problems, but in attempting to prove this, one gets stuck at the Haroutunian exponent because of entanglements between the channel behavior and the input distribution. In this paper, we present a characteristic of the Haroutunian exponent that differentiates it from the random coding and sphere-packing exponents. We consider the parallel channel, the repeated use of the original discrete memoryless channel independently some $L$ number of times. It is well known that the capacity of the parallel channel is $L$ times the capacity of the original channel, and the random coding and sphere-packing exponents of the $L$ -use parallel channel decompose into $L$ times the exponents of the original channel. The main result of this paper is to show that the (appropriately normalized) Haroutunian exponent of the parallel channel asymptotically decomposes to the sphere-packing exponent of the original channel, as opposed to the Haroutunian exponent of the original channel. This fact is then used to prove two results. First, an upper bound for the reliability function for fixed blocklength coding with delayed feedback is proved. This upper bound converges to the sphere-packing exponent as the delay in the feedback path tends to infinity. Second, the reliability function for fixed delay coding without feedback is shown to be upper bounded by the sphere-packing exponent. [ABSTRACT FROM PUBLISHER]

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A $(q,k,n)$ -Armstrong code is a $q$ -ary code of length $n$ with minimum Hamming distance $n-k+1$ , and for any set of $k-1$ coordinates, there exist two codewords that agree exactly there. Let $f(q,k)$ be the maximum $n$ for which such a code exists. In this paper, $f(q,3)=3q-1$ is determined for all $q\geq 5$ with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or $(s,t)$ -dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length $n$ in this more general setting. [ABSTRACT FROM AUTHOR]

In this paper, we extend the construction by Yu and Gong for families of M -ary sequences of period q-1 from the array structure of an M -ary Sidelnikov sequence of period , where q is a prime power and M|q-1 . The construction now applies to the cases of using any period for 3\leq d < ({1}/{2})(\sqrt {q}-({2}/{\sqrt {q}})+1) and q>27 . The proposed construction results in a family of M -ary seqeunces of period q-1 with: 1) the correlation magnitudes, which are upper bounded by and 2) the asymptotic size of (M-1)q^d-1/d as q increases. We also characterize some subsets of the above of size \sim (r-1)q^d-1/d but with a tighter upper bound (2d-2)\sqrt q+2 on its correlation magnitude. We discuss reducing both time and memory complexities for the practical implementation of such constructions in some special cases. We further give some approximate size of the newly constructed families in general and an exact count when $d$ is a prime power or a product of two distinct primes. The main results of this paper now give more freedom of tradeoff in the design of $M$ -ary sequence family between the family size and the correlation magnitude of the family. [ABSTRACT FROM PUBLISHER]

The sliding window Lempel–Ziv (SWLZ) algorithm that makes use of recurrence times and match lengths has been studied from various perspectives in information theory literature. In this paper, we undertake a finer study of these quantities under two different scenarios: 1) zero entropy sources that are characterized by strong long-term memory and 2) the processes with weak memory as described through various mixing conditions. For zero entropy sources, a general statement on match length is obtained. It is used in the proof of almost sure optimality of fixed shift variant of Lempel–Ziv (FSLZ) and SWLZ algorithms given in literature. Through an example of stationary and ergodic processes generated by an irrational rotation, we establish that for a window of size nw , a compression ratio given by O(\log nw/{{nw}^{a}}) , where $a$ depends on n_{w} \rightarrow \infty , is obtained under the application of FSLZ and SWLZ algorithms. In addition, we give a general expression for the compression ratio for a class of stationary and ergodic processes with zero entropy. Next, we extend the study of Ornstein and Weiss on the asymptotic behavior of the normalized version of recurrence times and establish the large deviation property for a class of mixing processes. In addition, an estimator of entropy based on recurrence times is proposed for which large deviation principle is proved for sources satisfying similar mixing conditions. [ABSTRACT FROM PUBLISHER]

We consider the $N$ -relay Gaussian diamond network where a source node communicates to a destination node via $N$ parallel relays through a cascade of a Gaussian broadcast (BC) and a multiple access (MAC) channel. Introduced in 2000 by Schein and Gallager, the capacity of this relay network is unknown in general. The best currently available capacity approximation, independent of the coefficients and the SNRs of the constituent channels, is within an additive gap of $1.3 N$ bits, which follows from the recent capacity approximations for general Gaussian relay networks with arbitrary topology. In this paper, we approximate the capacity of this network within 2 log $N$ bits. We show that two strategies can be used to achieve the information-theoretic cut-set upper bound on the capacity of the network up to an additive gap of $O(\log N)$ bits, independent of the channel configurations and the SNRs. The first of these strategies is simple partial decode-and-forward. Here, the source node uses a superposition codebook to broadcast independent messages to the relays at appropriately chosen rates; each relay decodes its intended message and then forwards it to the destination over the MAC channel. A similar performance can be also achieved with compress-and-forward type strategies (such as quantize-map-and-forward and noisy network coding) that provide the $1.3 N$ -bit approximation for general Gaussian networks, but only if the relays quantize their observed signals at a resolution inversely proportional to the number of relay nodes $N$ . This suggests that the rule-of-thumb to quantize the received signals at the noise level in the current literature can be highly suboptimal. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minimum energy of transmitting correlated sources over the Gaussian multiple-access channel. Compared to other works on joint source-channel coding, we consider the fundamental problem of the minimum transmission energy, where the source and channel bandwidths are not naturally matched. Different models of correlated sources are studied. We first treat lossy transmission of Gaussian sources, including multiterminal sources and CEO sources. We then consider lossless transmission of correlated binary sources. In all cases, we lower bound the minimum energy using a cut-set argument that couples transmission energy and the distortions for the Gaussian cases (or source entropy for the discrete case). For the achievable schemes, separate source and channel coding and uncoded transmission are studied as benchmarks. In addition, we show that hybrid digital/analog transmission achieves the best known energy efficiency. [ABSTRACT FROM AUTHOR]

A sufficient condition reported very recently for perfect recovery of a \(K\) -sparse vector via orthogonal matching pursuit (OMP) in \(K\) iterations (when there is no noise) is that the restricted isometry constant (RIC) of the sensing matrix satisfies \(\delta _{K+1} <({1}/{\sqrt {K} +1})\) . In the noisy case, this RIC upper bound along with a requirement on the minimal signal entry magnitude is known to guarantee exact support identification. In this paper, we show that, in the presence of noise, a relaxed RIC upper bound \(\delta _{K+1} <({\sqrt {4K+1} -1}/{2K})\) together with a relaxed requirement on the minimal signal entry magnitude suffices to achieve perfect support identification using OMP. In the noiseless case, our result asserts that such a relaxed RIC upper bound can ensure exact support recovery in \(K\) iterations: this narrows the gap between the so far best known bound \(\delta _{K+1} <({1}/{\sqrt {K} +1})\) and the ultimate performance guarantee \(\delta _{K+1} =({1}/{\sqrt {K}})\) . Our approach relies on a newly established near orthogonality condition, characterized via the achievable angles between two orthogonal sparse vectors upon compression, and, thus, better exploits the knowledge about the geometry of the compressed space. The proposed near orthogonality condition can be also exploited to derive less restricted sufficient conditions for signal reconstruction in two other compressive sensing problems, namely, compressive domain interference cancellation and support identification via the subspace pursuit algorithm. [ABSTRACT FROM PUBLISHER]

In this paper, an online learning algorithm is proposed as sequential stochastic approximation of a regularization path converging to the regression function in reproducing kernel Hilbert spaces (RKHSs). We show that it is possible to produce the best known strong (RKHS norm) convergence rate of batch learning, through a careful choice of the gain or step size sequences, depending on regularity assumptions on the regression function. The corresponding weak (mean square distance) convergence rate is optimal in the sense that it reaches the minimax and individual lower rates in this paper. In both cases, we deduce almost sure convergence, using Bernstein-type inequalities for martingales in Hilbert spaces. To achieve this, we develop a bias-variance decomposition similar to the batch learning setting; the bias consists in the approximation and drift errors along the regularization path, which display the same rates of convergence, and the variance arises from the sample error analyzed as a (reverse) martingale difference sequence. The rates above are obtained by an optimal tradeoff between the bias and the variance. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimax rates and provide an implementable convex algorithm for Poisson inverse problems under weak sparsity and physical constraints. In particular, we assume the model $y_{i} \sim \mathrm {Poisson}(Ta_{i}^{\top }f^{*})$ for $1 \leq i \leq n$ , where $T \in \mathbb {R}_{+}$ is the intensity, and we impose weak sparsity on $f^{*} \in \mathbb {R}^{p}$ by assuming $f^{*}$ lies in an $\ell _{q}$ -ball when rotated according to an orthonormal basis $D \in \mathbb {R}^{p \times p}$. In addition, since we are modeling real-physical systems, we also impose positivity and flux-preserving constraints on the matrix $A = [a_{1}, a_{2},\ldots, a_{n}]^{\top }$ and the function $f^{*}$. We prove minimax lower bounds for this model, which scale as $R_{q} ({\log p}/{T})^{1 - ({q}/{2})}$ where it is noticeable that the rate depends on the intensity $T$ and not the sample size $n$. We also show that an $\ell _{1}$ -based regularized least-squares estimator achieves this minimax lower bound, provided a suitable restricted eigenvalue condition is satisfied. Finally, we prove that provided $n \geq \tilde {K} \log p$ where $\tilde {K} = \Theta (R_{q} ({\log p}/{T})^{- ({q}/{2})})$ represents an approximate sparsity level, and our restricted eigenvalue condition and physical constraints are satisfied for random bounded ensembles. We also provide numerical experiments that validate our mean-squared error bounds. Our results address a number of open issues from prior work on Poisson inverse problems that focuses on strictly sparse models and does not provide guarantees for convex implementable algorithms. [ABSTRACT FROM AUTHOR]

For non-binary codes the Elias bound is a good upper bound for the asymptotic information rate at low-relative minimum distance, whereas the Plotkin bound is better at high-relative minimum distance. In this paper, we obtain a hybrid of these bounds, which improves both. This in turn is based on the anticode bound, which is a hybrid of the Hamming and Singleton bounds and improves both bounds. The question of convexity of the asymptotic rate function is an important open question. We conjecture a much weaker form of the convexity, and we show that our bounds follow immediately if we assume the conjecture. [ABSTRACT FROM AUTHOR]

The capability of a given channel to communicate information is, a priori, distinct from its capability to distribute shared randomness. In this paper, we define randomness distribution capacities of quantum channels assisted by forward, back, or two-way classical communication and compare these to the corresponding communication capacities. With forward assistance or no assistance, we find that they are equal. We establish the mutual information of the channel as an upper bound on the two-way assisted randomness distribution capacity. This implies that all of the capacities are equal for classical-quantum channels. On the other hand, we show that the back-assisted randomness distribution capacity of a quantum-classical channel is equal to its mutual information. This is often strictly greater than the back-assisted communication capacity. We give an explicit example of such a separation where the randomness distribution protocol is noiseless. [ABSTRACT FROM AUTHOR]

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k -threshold access structure, where the qualified subsets are those of size at least k . When k=2 and there are n parties, there are schemes for sharing an \ell bits, and this is tight even for secrets of 1 b. In these schemes, the number of parties n must be given in advance to the dealer. In this paper, we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the {t} {^{\mathrm{ th}}} party arriving the smallest possible share as a function of t$ . Our main result is such a scheme for the k$ -threshold access structure and 1-bit secrets where the share size of party t$ is . For k=2$ we observe an equivalence to prefix codes and present matching upper and lower bounds of the form \log t + \log \log t + \log \log \log t + O(1)$ . Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size . [ABSTRACT FROM AUTHOR]

A subspace of a finite extension field is called a Sidon space if the product of any two of its elements is unique up to a scalar multiplier from the base field. Sidon spaces were recently introduced by Bachoc et al. as a means to characterize multiplicative properties of subspaces, and yet no explicit constructions were given. In this paper, several constructions of Sidon spaces are provided. In particular, in some of the constructions the relation between $k$ , the dimension of the Sidon space, and $n$ , the dimension of the ambient extension field, is optimal. These constructions are shown to provide cyclic subspace codes, which are useful tools in network coding schemes. To the best of our knowledge, this constitutes the first set of constructions of non-trivial cyclic subspace codes in which the relation between $k$ and $n$ is polynomial, and in particular, linear. As a result, a conjecture by Trautmann et al. regarding the existence of non-trivial cyclic subspace codes is resolved for most parameters, and multi-orbit cyclic subspace codes are attained, whose cardinality is within a constant factor (close to 1/2) from the sphere-packing bound for subspace codes. [ABSTRACT FROM AUTHOR]

This paper examines fundamental error characteristics for a general class of matrix completion problems, where the matrix of interest is a product of two a priori unknown matrices, one of which is sparse, and the observations are noisy. Our main contributions come in the form of minimax lower bounds for the expected per-element squared error for this problem under several common noise models. Specifically, we analyze scenarios where the corruptions are characterized by additive Gaussian noise or additive heavier-tailed (Laplace) noise, Poisson-distributed observations, and highly-quantized (e.g., one bit) observations, as instances of our general result. Our results establish that the error bounds derived in (Soni et al., 2016) for complexity-regularized maximum likelihood estimators achieve, up to multiplicative constants and logarithmic factors, the minimax error rates in each of these noise scenarios, provided that the nominal number of observations is large enough, and the sparse factor has (on an average) at least one non-zero per column. [ABSTRACT FROM PUBLISHER]

A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets. [ABSTRACT FROM PUBLISHER]

Wachter-Zeh showed that every cover metric code can be list decoded up to the Johnson-like bound. Furthermore, it was shown that the efficient list decoding of cover metric codes up to the Johnson-like bound can be performed. From the work of Wachter-Zeh, one natural question is whether the Johnson-like bound can be improved. In this paper, we give a confirmative answer to this question by showing that the cover metric codes can be list decoded up to the Singleton bound. Our contributions consist of three parts. First, we prove that the list decodability of cover metric codes does not exceed the Singleton bound. Second, we show that, with high probability, a random cover metric code can be list decoded up to the Singleton bound, which is better than the Johnson-like bound. Third, by applying the existing decoding algorithms for Hamming metric and rank metric codes, we present explicit constructions of cover metric codes that can be efficiently list decoded up to the Singleton bound. [ABSTRACT FROM AUTHOR]

This paper investigates the convexity of the mean squared-error distortion of symmetric uniform scalar quantization with respect to step size. The principal results include proofs for odd numbers of levels that distortion is not convex for any symmetric density and that it is convex for even numbers of levels for densities, such as Gaussian, Laplacian, and gamma, but is not, in general for two-sided Rayleigh. For the latter case, an interval is derived that includes the optimal step size and over which the distortion is convex. The proofs of convexity use the Euler–Maclaurin formula applied to the second derivative of distortion, with upper bounds on the remainder term. These results imply that a zero of the derivative of the distortion for these densities, which has been previously conjectured optimal, is indeed the optimal step size, because the distortion is convex either globally or locally over a sufficiently wide interval to ensure a global minimizer. [ABSTRACT FROM AUTHOR]

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently. [ABSTRACT FROM PUBLISHER]

Let W=\w1, \ldots , wr\ be a set of positive integers, \lambda c a positive integer, \Lambda a=(\lambda a^{(1)}, \ldots \lambda a^{(r)}) an r -tuple of positive integers, and Q=(q_{1}, \ldots q_{r}) an r -tuple of positive rational numbers whose sum is 1. In 1996, Yang introduced variable-weight optical orthogonal code, (n, W, \Lambda a, \lambda c, Q) -OOC, for multimedia optical CDMA systems with multiple quality of service (QoS) requirements. Some work had been done on the constructions of optimal (n, W, \Lambda a, 1, Q) -OOCs with unequal auto-correlation constraints for W=\3, 4\ and {3, 5}, while little is known on optimal (n, W, \Lambda a, 1, Q) -OOCs for |W|\geq 3 . In this paper, we focus our main attentions on (n, \{3, 4, 5\}, \Lambda _{a}, 1, Q) -OOCs with \Lambda _{a}\in \{(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)\} . Tight upper bounds on the maximum code size of (n, \3, 4, 5\, \Lambda a, 1, Q) -OOCs are obtained, and infinite classes of optimal (n, \3, 4, 5\, \Lambda a, 1, Q) -OOCs are constructed. [ABSTRACT FROM PUBLISHER]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

The Johnson-type upper bound on the maximum size of a code of length n , distance d=2w-1 , and constant composition \overline w is \lfloor \dfrac \vphantom R^.nw1\rfloor , where w is the total weight and w_{1} is the largest component of {\overline {w}} . Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let Nccc({\overline {w}}) be the smallest such length. The determination of Nccc({\overline {w}}) is trivial for binary codes. This paper provides a lower bound on Nccc({\overline {w}}) , which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by the refining method, we determine the values of Nccc({\overline {w}}) , for all $q$ -ary constant-composition codes, provided that 3w_{1}\geq w with finite possible exceptions. [ABSTRACT FROM AUTHOR]

Reducible codes for the rank metric were introduced for cryptographic purposes. They have fast encoding and decoding algorithms, include maximum rank distance (MRD) codes, and can correct many rank errors beyond half of their minimum rank distance, which makes them suitable for error correction in network coding. In this paper, we study their security behavior against information leakage on networks when applied as coset coding schemes, giving the following main results: 1) we give lower and upper bounds on their generalized rank weights (GRWs), which measure worst case information leakage to the wire tapper; 2) we find new parameters for which these codes are MRD (meaning that their first GRW is optimal) and use the previous bounds to estimate their higher GRWs; 3) we show that all linear (over the extension field) codes, whose GRWs are all optimal for fixed packet and code sizes but varying length are reducible codes up to rank equivalence; and 4) we show that the information leaked to a wire tapper when using reducible codes is often much less than the worst case given by their (optimal in some cases) GRWs. We conclude with some secondary related properties: conditions to be rank equivalent to Cartesian products of linear codes and conditions to be rank degenerate, duality properties, and MRD ranks. [ABSTRACT FROM PUBLISHER]

Let X and Y be dependent random variables. This paper considers the problem of designing a scalar quantizer for Y to maximize the mutual information between the quantizer’s output and X, and develops fundamental properties and bounds for this form of quantization, which is connected to the log-loss distortion criterion. The main focus is the regime of low ${I}({X};{Y})$ , where it is shown that, if X is binary, a constant fraction of the mutual information can always be preserved using $\mathcal {O}(\log (1/{I}({X};{Y})))$ quantization levels, and there exist distributions for which this many quantization levels are necessary. Furthermore, for larger finite alphabets $2 < |\mathcal {X}| < \infty $ , it is established that an $\eta $ -fraction of the mutual information can be preserved using roughly $(\log (| \mathcal {X} | /{I}({X};{Y})))^{\eta \cdot (|\mathcal {X}| - 1)}$ quantization levels. [ABSTRACT FROM AUTHOR]

Time-varying spatially coupled low-density parity-check (SC-LDPC) codes with very large period are characterized by significantly better error rate performance and girth properties than their time-invariant counterparts, but the number of parameters they require to be described is usually very large and unpractical. Time-invariant SC-LDPC codes, which can be seen as periodically time-varying codes with unitary period, are represented through a small number of parameters and designed exploiting few degrees of freedom, but their error rate performance and girth properties are sub-optimal. In this paper, we show that the limits of time-invariant SC-LDPC codes can be overcome by transforming them into time-varying SC-LDPC codes with very small period. In particular, we show that periodically time-varying SC-LDPC codes with small period may exhibit significantly better girth properties than the corresponding time-invariant codes by exploiting a larger number of degrees of freedom in the code design, which however scale at most linearly with the product of the code period and the size of the considered base matrix. [ABSTRACT FROM AUTHOR]

We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. In particular, it is shown that if the rate exceeds the upper-bound, the probability of error tends to one exponentially when the block-length tends to infinity. We also show that the underlying optimization problem is a convex-concave problem and that an efficient iterative algorithm converges to the optimal solution. In addition, we show that, unlike achievable rates in the literature, the multiletter version of the bound cannot not improve. A number of examples are discussed throughout the paper. [ABSTRACT FROM AUTHOR]

In this paper upper and lower bounds on the probability of decoding failure under maximum likelihood decoding are derived for different (nonbinary) Raptor code constructions. In particular four different constructions are considered; (i) the standard Raptor code construction, (ii) a multi-edge type construction, (iii) a construction where the Raptor code is nonbinary but the generator matrix of the LT code has only binary entries, (iv) a combination of (ii) and (iii). The latter construction resembles the one employed by RaptorQ codes, which at the time of writing this article represents the state of the art in fountain codes. The bounds are shown to be tight, and provide an important aid for the design of Raptor codes. [ABSTRACT FROM AUTHOR]

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that a complementary channel can be obtained from the channel by applying a degrading channel. In this paper, we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite $\varepsilon \geq 0$ . That is, there exists a degrading channel which upon composition with the channel is $\varepsilon $ -close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such $\varepsilon $ can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication. [ABSTRACT FROM AUTHOR]

In this paper, we consider communication on a two-hop channel in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper, and there is a cooperative node, which sends a jamming signal to confuse the relay when it is receiving from the source. In the external eavesdropper case, the relay is trusted, and there is an external node eavesdropping the communication. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code, and the other one is based on a lattice chain code. It is proved that in the high signal-to-noise-ratio (SNR) scenario and/or the limited relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely 1/2 bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper. [ABSTRACT FROM AUTHOR]

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length N$ over an alphabet of size q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when q$ is small compared with w$ , say cq\leq w$ for some constant c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary w . [ABSTRACT FROM PUBLISHER]

The capacity region of the $K$ -user Gaussian interference channel (GIC) is a long-standing open problem and even capacity outer bounds are little known in general. A significant progress on degrees-of-freedom (DoF) analysis, a first-order capacity approximation, for the $K$ -user GIC has provided new important insights into the problem of interest in the high signal-to-noise ratio (SNR) limit. However, such capacity approximation has been observed to have some limitations in predicting the capacity at finite SNR. In this paper, we develop a new upper-bounding technique that utilizes a new type of genie signal and applies time sharing to genie signals at $K$ receivers. Based on this technique, we derive new upper bounds on the sum capacity of the three-user GIC with constant, complex channel coefficients and then generalize to the $K$ -user case to better understand sum-rate behavior at finite SNR. We also provide closed-form expressions of our upper bounds on the capacity of the $K$ -user symmetric GIC easily computable for any $K$ . From the perspectives of our results, some sum-rate behavior at finite SNR is in line with the insights given by the known DoF results, while some others are not. In particular, the well-known $K/2$ DoF achievable for almost all constant real channel coefficients turns out to be not embodied as a substantial performance gain over a certain range of the cross-channel coefficient in the $K$ -user symmetric real case especially for large $K$ . We further investigate the impact of phase offset between the direct-channel coefficient and the cross-channel coefficients on the sum-rate upper bound for the three-user complex GIC. As a consequence, we aim to provide new findings that could not be predicted by the prior works on DoF of GICs. [ABSTRACT FROM PUBLISHER]

Caching is a promising solution to satisfy the ever-increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into F packets, which usually increases exponentially with the number of users K . Thus, designing caching schemes that decrease the order of F is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least F . Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (identical cache size is assumed at all users) and the number of files N ( q is an integer, such that q\geq 2 ). The new construction can decrease the required F of Ali-Niesen scheme to O(e^{K\cdot ({M}/{N})\ln \!\,({N}/\!{M})}) or O(e^{K\cdot (1-({M}/\!{N}))\ln \!\,(N/(N-M))})$ , respectively, while the coding gain loss is only 1. [ABSTRACT FROM AUTHOR]

A phase detection sequence is a length- $n$ cyclic sequence, such that the location of any length- $k$ contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible $k$ in the limit of $n\to \infty $ , and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length- $k$ contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed. [ABSTRACT FROM AUTHOR]

We prove new strong converse results in a variety of group testing settings, generalizing a result of Baldassini et al.. First, in the non-adaptive case, we mimic the hypothesis testing argument introduced in the finite blocklength channel coding regime by Polyanskiy et al., and using joint source–channel coding arguments of Kostina and Verdú. In the adaptive case, we combine this approach with a novel model formulation based on causal probability and directed information theory. In both cases, we prove results, which are valid for finite sized problems, and imply capacity results in the asymptotic regime. These results are illustrated graphically for a range of models. [ABSTRACT FROM AUTHOR]

This paper considers the two-user Gaussian causal cognitive interference channel (GCCIC), which consists of two source-destination pairs that share the same channel and where one full-duplex cognitive source can causally learn the message of the primary source through a noisy link. The GCCIC is an interference channel with unilateral source cooperation that better models practical cognitive radio networks than the commonly used model which assumes that one source has perfect noncausal knowledge of the other source's message. First, the sum-capacity of the symmetric GCCIC is determined to within a constant gap. Then, the insights gained from the study of the symmetric GCCIC are extended to more general cases. In particular, the whole capacity region of the Gaussian Z-channel, i.e., when there is no interference from the primary user, and of the Gaussian S-channel, i.e., when there is no interference from the secondary user, are both characterized to within 2 bits. The fully connected general, i.e., no-symmetric, GCCIC is also considered and its capacity region is characterized to within 2 bits when, roughly speaking, the interference is not weak at both receivers. The parameter regimes where the GCCIC is equivalent, in terms of generalized degrees-of-freedom, to the noncooperative interference channel (i.e., unilateral causal cooperation is not useful), to the non-causal cognitive interference channel (i.e., causal cooperation attains the ultimate limit of cognitive radio technology), and to bilateral source cooperation are identified. These comparisons shed light into the parameter regimes and network topologies that in practice might provide an unbounded throughput gain compared to currently available (non cognitive) technologies. [ABSTRACT FROM AUTHOR]

Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e., the memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared with previously known schemes. In particular, the improvement can be on the order of the number of users in the network. In addition, we argue that the performance of the proposed scheme is within a constant factor of the information-theoretic optimum for all values of the problem parameters. [ABSTRACT FROM AUTHOR]

The small sample universal hypothesis testing problem is investigated in this paper, in which the number of samples n is smaller than the number of possible outcomes m. The goal of this paper is to find an appropriate criterion to analyze statistical tests in this setting. A suitable model for analysis is the high-dimensional model in which both n and m increase to infinity, and n=o(m). A new performance criterion based on large deviations analysis is proposed and it generalizes the classical error exponent applicable for large sample problems (in which m=O(n)). This generalized error exponent criterion provides insights that are not available from asymptotic consistency or central limit theorem analysis. The following results are established for the uniform null distribution: 1) The best achievable probability of error Pe decays as Pe=\exp \{-(n^{2}/m) J (1+o(1))\} for some J>0. 2) A class of tests based on separable statistics, including the coincidence-based test, attains the optimal generalized error exponents. 3) Pearson's chi-square test has a zero generalized error exponent and thus its probability of error is asymptotically larger than the optimal test. [ABSTRACT FROM PUBLISHER]

In this paper, lower bounds on error probability in coding for discrete classical and classical-quantum channels are studied. The contribution of the paper goes in two main directions: 1) extending classical bounds of Shannon to classical-quantum channels, and 2) proposing a new framework for lower bounding the probability of error of channels with a zero-error capacity in the low rate region. The relation between these two problems is revealed by showing that Lovász' bound on zero-error capacity emerges as a natural consequence of the sphere packing bound once we move to the more general context of classical-quantum channels. A variation of Lovász' bound is then derived to lower bound the probability of error in the low rate region by means of auxiliary channels. As a result of this study, connections between the Lovász theta function, the expurgated bound of Gallager, the cutoff rate of a classical channel, and the sphere packing bound for classical-quantum channels are established. [ABSTRACT FROM PUBLISHER]

Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is $\boldsymbol {b}$ , the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing $\boldsymbol {b}$ is NP-complete, a popular gold standard is $\boldsymbol {z}$ , the number of phrases in the Lempel-Ziv parse of the text, which is computed in linear time and yields the least number of phrases when those can be copied only from the left. Almost nothing has been known for decades about the approximation ratio of $\boldsymbol {z}$ with respect to $\boldsymbol {b}$. In this paper we prove that $z=O(b\log (n/b))$ , where $n$ is the text length. We also show that the bound is tight as a function of $n$ , by exhibiting a text family where $z = \Omega (b\log n)$. Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating $\boldsymbol {b}$ with $r$ , the number of equal-letter runs in the Burrows-Wheeler transform of the text. We continue by observing that Lempel-Ziv is just one particular case of greedy parses–meaning that it obtains the smallest parse by scanning the text and maximizing the phrase length at each step–, and of ordered parses–meaning that phrases are larger than their sources under some order. As a new example of ordered greedy parses, we introduce lexicographical parses, where phrases can only be copied from lexicographically smaller text locations. We prove that the size $v$ of the optimal lexicographical parse is also obtained greedily in $O(n)$ time, that $v=O(b\log (n/b))$ , and that there exists a text family where $v = \Omega (b\log n)$. Interestingly, we also show that $v = O(r)$ because $r$ also induces a lexicographical parse, whereas $z = \Omega (r\log n)$ holds on some text families. We obtain some results on parsing complexity and size that hold on some general classes of greedy ordered parses. In our way, we also prove other relevant bounds between compressibility measures, especially with those related to smallest grammars of various types generating (only) the text. [ABSTRACT FROM AUTHOR]

In this paper, we study the sparse linear regression problem under the Local Differential Privacy (LDP) model. We first show that polynomial dependency on the dimensionality $p$ of the space is unavoidable for the estimation error in both non-interactive and sequential interactive local models, if the privacy of the whole dataset needs to be preserved. Similar limitations also exist for other types of error measurements and in the relaxed local models. This indicates that differential privacy in high dimensional space is unlikely achievable for the problem. With the understanding of this limitation, we then present two algorithmic results. The first one is a sequential interactive LDP algorithm for the low dimensional sparse case, called Locally Differentially Private Iterative Hard Thresholding (LDP-IHT), which achieves a near optimal upper bound. This algorithm is actually rather general and can be used to solve quite a few other problems, such as (Local) DP-ERM with sparsity constraints and sparse regression with non-linear measurements. The second one is for the restricted (high dimensional) case where only the privacy of the responses (labels) needs to be preserved. For this case, we show that the optimal rate of the error estimation can be made logarithmically dependent on $p$ (i.e., $\log p$) in the local model, where an upper bound is obtained by a label-privacy version of LDP-IHT. Experiments on real world and synthetic datasets confirm our theoretical analysis. [ABSTRACT FROM AUTHOR]

A locally repairable code (LRC) is a linear code such that every code symbol can be recovered by accessing a small number of other code symbols. In this paper, we study bounds and constructions of LRCs from the viewpoint of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed, and several new explicit bounds on the minimum distance of LRCs in terms of the field size are presented. In particular, we give an alternate proof of the Singleton-like bound for LRCs first proved by Gopalan et al. Some structural properties on optimal LRCs that achieve the Singleton-like bound are given. Then, we focus on constructions of optimal LRCs over the binary field. It is proved that there are only five classes of possible parameters with which optimal binary LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these five classes of optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes. [ABSTRACT FROM AUTHOR]