Search

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]

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]

Estimating Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the $k$ nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator. Furthermore, we derive a lower bound of the minimax mean square error and show that kNN method is asymptotically rate optimal. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) and codes with hierarchical locality (H-LRCs) have a great significance due to their applications in distributed storage systems. Constructing LRCs or H-LRCs achieving the Singleton-type bound is a challenging task and has received much attention. In this paper, we make use of optimal LRCs to construct a family of optimal H-LRCs. For this purpose we first construct a new class of optimal LRCs via generalized Reed-Solomon codes (GRS codes). Next, based on these optimal LRCs we present some new optimal H-LRCs, of which the parameters are more flexible than those given in and. [ABSTRACT FROM AUTHOR]

We propose inhomogeneous random K-out graphs $\mathbb {H}(n; {\mu }, {K}_{n})$ , where each of the $n$ nodes is assigned to one of $r$ classes independently with a probability distribution ${\mu } = \{\mu _{1}, \ldots, \mu _{r}\}$. In particular, each node is classified as class $i$ with probability $\mu _{i}>0$ , independently. With ${K}_{n} = \left ({K_{1,n}, \ldots, K_{r,n} }\right)$ , each class $i$ node selects $K_{i,n}$ distinct nodes uniformly at random from among all other nodes. A pair of nodes are adjacent in $\mathbb {H}(n; {\mu }, {K}_{n})$ if at least one selects the other. Without loss of generality, we assume that $K_{1,n} \leq K_{2,n} \leq \ldots \leq K_{r,n}$. Earlier results on homogeneous random K-out graphs $\mathbb {H}(n; K_{n})$ , where all nodes select the same number $K$ of other nodes, reveal that $\mathbb {H}(n; K_{n})$ is connected with high probability (whp) if $K_{n} \geq 2$ which implies that $\mathbb {H}(n; {\mu }, {K}_{n})$ is connected whp if $K_{1,n} \geq 2$. In this paper, we investigate the connectivity of inhomogeneous random K-out graphs $\mathbb {H}(n; {\mu }, {K}_{n})$ for the special case when $K_{1,n}=1$ , i.e., when each class 1 node selects only one other node. We show that $\mathbb {H}\left ({n;{\mu },{K}_{n}}\right)$ is connected whp if $K_{r,n}$ is chosen such that $\lim _{n \to \infty } K_{r,n} = \infty $. However, any bounded choice of the sequence $K_{r,n}$ gives a positive probability of $\mathbb {H}\left ({n;{\mu },{K}_{n}}\right)$ being asymptotically not connected in the limit of large $n$. Simulation results are provided to validate our results in the finite node regime. [ABSTRACT FROM AUTHOR]

Constant dimension codes (CDCs), as special subspace codes, have received a lot of attention due to their application in random network coding. This paper introduces a family of new codes, called rank metric codes with given ranks (GRMCs), to generalize the parallel construction in [Xu and Chen, IEEE Trans. Inf. Theory, 64 (2018), 6315–6319] and the classic multilevel construction. A Singleton-like upper bound and a lower bound for GRMCs derived from Gabidulin codes are given. Via GRMCs, two effective constructions for CDCs are presented by combining the parallel construction and the multilevel construction. Many CDCs with larger size than the previously best known codes are given. The ratio between the new lower bound and the known upper bound for $(4\delta,2\delta,2\delta)_{q}$ -CDCs is calculated. It is greater than 0.99926 for any prime power $q$ and any $\delta \geq 3$. [ABSTRACT FROM AUTHOR]

A Locally Recoverable Code is a code such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other coordinates. When we have $\delta $ non-overlapping subsets of cardinality $r_{i}$ that can be used to recover the missing coordinate we say that a linear code $\mathcal {C}$ with length $n$ , dimension $k$ , minimum distance $d$ has $(r_{1},\ldots, r_\delta)$ -locality and denote by $[n, k, d; r_{1}, r_{2}, {\dots }, r_\delta]$. In this paper we provide a new upper bound for the minimum distance of these codes. Working with a finite number of subgroups of cardinality $r_{i}+1$ of the automorphism group of a function field $\mathcal {F}| \mathbb {F}_{q}$ of genus $g \geq 1$ we propose a construction of $[n, k, d; r_{1}, r_{2}, {\dots }, r_\delta]$ -codes and apply the results to some well known families of function fields. [ABSTRACT FROM AUTHOR]

Self-orthogonal codes are an interesting type of linear codes due to their wide applications in communication and cryptography. It is known that self-orthogonal codes are often used to construct quantum error-correcting codes, which can protect quantum information in quantum computations and quantum communications. Let $\mathcal C$ be an $[n, k]$ cyclic code over $\mathbb {F}_{q}$ , where $\mathbb {F}_{q}$ is the finite field of order $q$. The hull of $\mathcal C$ is defined to be the intersection of the code and its dual. In this paper, we will employ the defining sets of cyclic codes to present two general characterizations of the hulls that have dimension $k-1$ or $k^\perp -1$ , where $k^\perp $ is the dimension of the dual code $\mathcal C^\perp $. Several sufficient and necessary conditions for primitive and projective BCH codes to have $(k-1)$ -dimensional (or $(k^\perp -1)$ -dimensional) hulls are also developed by presenting lower and upper bounds on their designed distances. Furthermore, several classes of self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated. The dimensions and minimum distances of some self-orthogonal codes are determined explicitly. In addition, several optimal codes are obtained. [ABSTRACT FROM AUTHOR]

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed and cloud storage systems. However, there are few asymptotic constructions of locally repairable codes in the literature. In this paper, we provide a new explicit asymptotic construction of locally repairable codes over arbitrary finite fields from local expansions of functions at a rational place. This construction gives a Tsfasman-Vladut-Zink type bound for locally repairable codes. Its main advantage is that there are no constraints on both locality and alphabet size. Furthermore, we show that the Gilbert-Varshamov type bound of locally repairable codes over non-prime finite fields can be improved for sufficiently large alphabet sizes. [ABSTRACT FROM AUTHOR]

The best outer bound on the capacity region of the two-user Gaussian interference channel (GIC) is known to be the intersection of regions of various bounds, including genie-aided outer bounds, in which a genie provides noisy input signals to the intended receiver. The Han and Kobayashi (HK) scheme provides the best known inner bound. The rate difference between the best known lower and upper bounds on the sum capacity remains as large as 1 b/channel use, especially around g^2=P^-1/3 , where P is the symmetric power constraint and g is the symmetric real cross-channel coefficient. In this paper, we pay attention to the moderate interference regime where g^2\in ~(\max (0.086, P^-1/3),1) . We propose a new upper-bounding technique that utilizes noisy observation of interfering signals as genie signals and applies time sharing to the genie signals at the receivers. A conditional version of the worst additive noise lemma is also introduced to derive new capacity bounds. The resulting upper (outer) bounds on the sum capacity (capacity region) are shown to be tighter than the existing bounds in a certain range of the moderate interference regime. Using the new upper bounds and the HK lower bound, we show that R\text {sym}^{ }=\frac {1}2\log \big (|g|P+|g|^{-1}(P+1)\big ) characterizes the capacity of the symmetric real GIC to within 0.104 b/channel use in the moderate interference regime at any signal-to-noise ratio (SNR). We further establish a high-SNR characterization of the symmetric real GIC, where the proposed upper bound is at most 0.1 b far from a certain HK achievable scheme with Gaussian signalling and time sharing for g^2\in ~(0,1] . In particular, R\text {sym}^{ } is achievable at high SNR by the proposed HK scheme and turns out to be the high-SNR capacity at least at g^2=0.25, 0.5 . We finally point out that there are two subregimes at high SNR in the weak interference regime, where g^2\in (0,1] . [ABSTRACT FROM AUTHOR]

The capacity-achieving input distribution of the discrete-time, additive white Gaussian noise (AWGN) channel with an amplitude constraint is discrete and seems difficult to characterize explicitly. A dual capacity expression is used to derive analytic capacity upper bounds for scalar and vector AWGN channels. The scalar bound improves on McKellips’ bound and is within 0.1 bit of capacity for all signal-to-noise ratios (SNRs). The 2-D bound is within 0.15 bits of capacity provably up to 4.5 dB; numerical evidence suggests a similar gap for all SNRs. As the SNR tends to infinity, these bounds are accurate and match with a volume-based lower bound. For the 2-D complex case, an analytic lower bound is derived by using a concentric constellation and is shown to be within 1 bit of capacity. [ABSTRACT FROM PUBLISHER]

Suppose Y^n is obtained by observing a uniform Bernoulli random vector X^n through a binary symmetric channel. Courtade and Kumar asked how large the mutual information between Y^n and a Boolean function \mathsf b(X^n) could be, and conjectured that the maximum is attained by a dictator function. An equivalent formulation of this conjecture is that dictator minimizes the prediction cost in a sequential prediction of Y^n under logarithmic loss, given \mathsf b(X^n) . In this paper, we study the question of minimizing the sequential prediction cost under a different (proper) loss function—the quadratic loss. In the noiseless case, we show that majority asymptotically minimizes this prediction cost among all Boolean functions. We further show that for weak noise, majority is better than a dictator, and that for a strong noise dictator outperforms majority. We conjecture that for quadratic loss, there is no single sequence of Boolean functions that is simultaneously (asymptotically) optimal at all noise levels. [ABSTRACT FROM PUBLISHER]

This paper establishes several converse bounds on the private transmission capabilities of a quantum channel. The main conceptual development builds firmly on the notion of a private state, which is a powerful, uniquely quantum method for simplifying the tripartite picture of privacy involving local operations and public classical communication to a bipartite picture of quantum privacy involving local operations and classical communication. This approach has previously led to some of the strongest upper bounds on secret key rates, including the squashed entanglement and the relative entropy of entanglement. Here, we use this approach along with a “privacy test” to establish a general meta-converse bound for private communication, which has a number of applications. The meta-converse allows for proving that any quantum channel’s relative entropy of entanglement is a strong converse rate for private communication. For covariant channels, the meta-converse also leads to second-order expansions of relative entropy of entanglement bounds for private communication rates. For such channels, the bounds also apply to the private communication setting in which the sender and the receiver are assisted by unlimited public classical communication, and as such, they are relevant for establishing various converse bounds for quantum key distribution protocols conducted over these channels. We find precise characterizations for several channels of interest and apply the methods to establish converse bounds on the private transmission capabilities of all phase-insensitive bosonic channels. [ABSTRACT FROM PUBLISHER]

Treating interference as noise (TIN) as the most appropriate approach in dealing with interference and the conditions on its optimality has attracted the interest of researchers recently. However, our knowledge on necessary and sufficient conditions of TIN is restricted to a few setups with limited number of users. In this paper, we study the optimality of TIN in terms of the generalized degrees of freedom (GDoF) for a fundamental network, namely, the $M\times 2$ X-channel. To this end, the achievable GDoF of TIN with power allocations at the transmitters is studied. It turns out that the transmit power allocation maximizing the achievable GDOF is given by on–off signaling as long as the receivers use TIN. This leads to two variants of TIN, namely, P2P-TIN and 2-IC-TIN. While in the first variant the $M\times 2$ X-channel is reduced to a point-to-point (P2P) channel, in the second variant, the setup is reduced to a two-user interference channel in which the receivers use TIN. The optimality of these two variants is studied separately. To this end, novel genie-aided upper bounds on the capacity of the X-channel are established. The conditions on the optimality of P2P-TIN can be summarized as follows. P2P-TIN is GDoF-optimal if there exists a dominant multiple access channel or a dominant broadcast channel embedded in the X channel. Furthermore, the necessary and sufficient conditions on the GDoF-optimality of 2-IC-TIN are presented. Interestingly, it turns out that operating the $M\times 2$ X-channel in the 2-IC-TIN mode might be still GDOF optimal, although the conditions given by Geng et al. are violated. However, 2-IC-TIN is sub-optimal if there exists a single interferer which causes sufficiently strong interference at both receivers. The comparison of the results with the state of the art shows that the GDOF optimality of TIN is expanded significantldy. [ABSTRACT FROM PUBLISHER]

The impact of cooperation on interference management is investigated by studying an elemental wireless network, the so-called symmetric interference relay channel (IRC), from a generalized degrees of freedom (GDoF) perspective. This is motivated by the fact that the deployment of relays is considered as a remedy to overcome the bottleneck of current systems in terms of achievable rates. The focus of this paper is on the regime in which the interference link is weaker than the source-relay link in the IRC. Our approach toward studying the GDoF goes through the capacity analysis of the linear deterministic IRC (LD-IRC). New upper bounds on the sum capacity of the LD-IRC based on genie-aided approaches are established. These upper bounds together with some existing upper bounds are achieved by using four novel transmission schemes. Extending the upper bounds and the transmission schemes to the Gaussian case, the GDoF of the Gaussian IRC is characterized for the aforementioned regime. This completes the GDoF results available in the literature for the symmetric GDoF. It turns out that even if the incoming and outgoing links of the relay are both weaker than the desired channel, involving a relay can increase the GDoF. Interestingly, utilizing the relay in this case can increase the slope of the GDoF from −2 [in the interference channel (IC)] to −1 or 0. This shrinks the regime where ignoring the interference by treating it as noise is optimal. Furthermore, the analysis shows that if the relay ingoing and outgoing links are sufficiently strong, the relay is able to neutralize the interference completely. In this case, the bottleneck of the transmission will be the interference links, and hence, the GDoF increases if the interference link gets stronger. It is shown that in the strong interference regime, in contrast to the IC, the GDoF can be a monotonically decreasing function of the interference level. [ABSTRACT FROM PUBLISHER]

In this paper, we consider optimal q -ary cyclic constant-weight codes of length n , minimum distance d , and weight w codes. We introduce the pure and mixed difference method to present a combinatorial description for a cyclic (n,d,w)_{q} code and then obtain some tight upper bounds on the sizes of optimal cyclic (n,d,w)_{q} codes. Finally, by using Skolem-type sequences, we completely determine the sizes of optimal cyclic (n,d,3)3 codes with minimum distance 1\leq d\leq 6 . [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2\sum i=1^{m}wi-2 or $2mw-2w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely. [ABSTRACT FROM AUTHOR]