Search

This paper studies low-latency streaming codes for the multi-hop network. The source transmits a sequence of messages to a destination through a chain of relays, and requires the destination to reconstruct each message by its deadline. We assume that each communication link is subjected to a certain maximum number of packet erasures. The case of a single relay (a three-node network) was considered in Fong et al. (2020). A coding scheme known as symbol-wise decode and forward was proposed. In the present work, we propose an alternative scheme that is different from Fong et al. (2020) and still achieves the same rate as in Fong et al. (2020) for the one hop case as the field-size goes to infinity. Furthermore, our proposed scheme naturally generalizes to the case of multiple-relay nodes yielding new achievable rates for this setting. The main difference with Fong et al. (2020) is that our proposed scheme exploits the ability of the relay nodes to adapt the transmission based on the erasures on the previous link. Hence, we refer to our scheme as “state-dependent” and contrast it with the scheme in Fong et al. (2020) that is state-independent. Our scheme requires the relay nodes to append a header to the transmitted packets, and we show that the size of the header does not depend on the field-size of the code. We also derive an upper bound on the maximal streaming rate achievable over a network with an arbitrary number of relays. We show that this upper bound matches our achievable rate in the special case when the maximal number of erasures on the first link is greater than or equal to the maximal number of erasures on each of the following links, and the field size goes to infinity. [ABSTRACT FROM AUTHOR]

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes. [ABSTRACT FROM AUTHOR]

This paper investigates the relation between three different notions of privacy: identifiability, differential privacy, and mutual-information privacy. Under a unified privacy-distortion framework, where the distortion is defined to be the expected Hamming distance between the input and output databases, we establish some fundamental connections between these three privacy notions. Given a maximum allowable distortion D , we define the privacy-distortion functions \epsilon _{\mathrm{ i}}^{*}(D) , \epsilon _{\mathrm{ d}}^{*}(D) , and \epsilon \mathrm{ m}^{*}(D) to be the smallest (most private/best) identifiability level, differential privacy level, and mutual information between the input and the output, respectively. We characterize \epsilon \mathrm{ i}^{*}(D) and \epsilon \mathrm{ d}^{*}(D) , and prove that \epsilon \mathrm{ i}^{*}(D)-\epsilon X\le \epsilon \mathrm{ d}^{*}(D)\le \epsilon \mathrm{ i}^{*}(D) for D within certain range, where \epsilon _{X} is a constant determined by the prior distribution of the original database X , and diminishes to zero when X is uniformly distributed. Furthermore, we show that \epsilon _{\mathrm{ i}}^{*}(D) and \epsilon _{\mathrm{ m}}^{*}(D)$ can be achieved by the same mechanism for D$ within certain range, i.e., there is a mechanism that simultaneously minimizes the identifiability level and achieves the best mutual-information privacy. Based on these two connections, we prove that this mutual-information optimal mechanism satisfies \epsilon $ -differential privacy with . The results in this paper reveal some consistency between two worst case notions of privacy, namely, identifiability and differential privacy, and an average notion of privacy, mutual-information privacy. [ABSTRACT FROM PUBLISHER]

This paper studies reconstruction of strings based upon their substrings spectrum. Under this paradigm, it is assumed that all substrings of some fixed length are received and the goal is to reconstruct the string. While many existing works assumed that substrings are received error free, we follow in this paper the noisy setup of this problem that was first studied by Gabrys and Milenkovic. The goal of this study is twofold. First we study the setup in which not all substrings in the multispectrum are received, and then we focus on the case where the read substrings are not error free. In each case we provide specific code constructions of strings that their reconstruction is guaranteed even in the presence of failure in either model. We present efficient encoding and decoding maps and analyze the cardinality of the code constructions, while studying the cases where the rates of our codes approach 1. [ABSTRACT FROM AUTHOR]

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated with the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large. [ABSTRACT FROM AUTHOR]

In this paper, we apply two-to-one functions over F2n in two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t + x)e with gcd (t, n) = gcd(e, 2n−1) = 1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters. [ABSTRACT FROM AUTHOR]

The inverse function x → x−1 on F2n, is one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x−1) + L2(x) over F2n if n ≥ 5, where L1,L2 are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics. [ABSTRACT FROM AUTHOR]

The article focuses on the author's information for publishing policies with the transmission, processing, and utilization of paper of the periodical in the issue 2019.

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as $O\left({\sqrt {\frac{k \log n }{ m}}}\right)$ , where $k$ , $m$ and $n$ denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as $O\left({{\frac{k \log n }{ m}}}\right)$ , suggests that if the signal class is structured (i.e., $k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the generalization performance of the Iterative Hard Thresholding (IHT) algorithm widely used for sparse recovery problems. The parameter estimation and sparsity recovery consistency of IHT has long been known in compressed sensing. From the perspective of statistical learning, another fundamental question is how well the IHT estimation would predict on unseen data. This paper makes progress towards answering this open question by introducing a novel sparse generalization theory for IHT under the notion of algorithmic stability. Our theory reveals that: 1) under natural conditions on the empirical risk function over $n$ samples of dimension $p$ , IHT with sparsity level $k$ enjoys an $\tilde {\mathcal {O}}(n^{-1/2}\sqrt {k\log (n)\log (p)})$ rate of convergence in sparse excess risk; 2) a tighter $\tilde {\mathcal {O}}(n^{-1/2}\sqrt {\log (n)})$ bound can be established by imposing an additional iteration stability condition on a hypothetical IHT procedure invoked to the population risk; and 3) a fast rate of order $\tilde {\mathcal {O}}\left ({n^{-1}k(\log ^{3}(n)+\log (p))}\right)$ can be derived for strongly convex risk function under proper strong-signal conditions. The results have been substantialized to sparse linear regression and sparse logistic regression models to demonstrate the applicability of our theory. Preliminary numerical evidence is provided to support our theoretical predictions. [ABSTRACT FROM AUTHOR]

This paper proposes using the uncertainty of information (UoI), measured by Shannon’s entropy, as a metric for information freshness. We consider a system in which a central monitor observes M binary Markov processes through m communication channels (m

In the coded caching problem, as originally formulated by Maddah-Ali and Niesen, a server communicates via a noiseless shared broadcast link to multiple users that have local storage capability. In order for a user to decode its demanded file from the coded multicast transmission, the demands of all the users must be globally known, which may violate the privacy of the users. To overcome this privacy problem, Wan and Caire recently proposed several schemes that attain coded multicasting gain while simultaneously guarantee information theoretic privacy of the users’ demands. In Device-to-Device (D2D) networks, the demand privacy problem is further exacerbated by the fact that each user is also a transmitter, which appears to be needing the knowledge of the files demanded by the remaining users in order to form its coded multicast transmission. This paper shows how to solve this seemingly infeasible problem. The main contribution of this paper is the development of new achievable and converse bounds for D2D coded caching that are to within a constant factor of one another when privacy of the users’ demands must be guaranteed even in the presence of colluding users (i.e., when some users share cached contents and demanded file indices). First, a D2D private caching scheme is proposed, whose key feature is the addition of virtual users in the system in order to “hide” the demands of the real users. By comparing the achievable D2D private load with an existing converse bound for the shared-link model without demand privacy constraint, the proposed scheme is shown to be order optimal, except for the very low memory size regime with more files than users. Second, in order to shed light into the open parameter regime, a new achievable scheme and a new converse bound under the constraint of uncoded cache placement (i.e., when each user stores directly a subset of the bits of the library) are developed for the case of two users, and shown to be to within a constant factor of one another for all system parameters. Finally, the two-user converse bound is extended to any number of users by a cut-set type argument. With this new converse bound, the virtual users scheme is shown to be order optimal in all parameter regimes under the constraint of uncoded cache placement and user collusion. [ABSTRACT FROM AUTHOR]

It is well known that for Gaussian channels, a nearest neighbor decoding rule, which seeks the minimum Euclidean distance between a codeword and the received channel output vector, is the maximum likelihood solution and hence capacity-achieving. Nearest neighbor decoding remains a convenient and yet mismatched solution for general channels, and the key message of this paper is that the performance of nearest neighbor decoding can be improved by generalizing its decoding metric to incorporate channel state dependent output processing and codeword scaling. Using generalized mutual information, which is a lower bound to the mismatched capacity under independent and identically distributed codebook ensemble, as the performance measure, this paper establishes the optimal generalized nearest neighbor decoding rule, under Gaussian channel input. Several restricted forms of the generalized nearest neighbor decoding rule are also derived and compared with existing solutions. The results are illustrated through several case studies for fading channels with imperfect receiver channel state information and for channels with quantization effects. [ABSTRACT FROM AUTHOR]

ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinho et al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218 and $2^{228.51}$ respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim. [ABSTRACT FROM AUTHOR]

This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22. [ABSTRACT FROM AUTHOR]

In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari, we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the non-stable case, with a special focus on Lévy processes that are locally self-similar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal–Getoor index. [ABSTRACT FROM AUTHOR]

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

In 1991, Wei proved a duality theorem that established an interesting connection between the generalized Hamming weights of a linear code and those of its dual code. Wei’s duality theorem has since been extensively studied from different perspectives and extended to other settings. In this paper, we re-examine Wei’s duality theorem and its various extensions, henceforth referred to as Wei-type duality theorems, from a new Galois connection perspective. Our approach is based on the observation that the generalized Hamming weights and the dimension/length profiles of a linear code form a Galois connection. The central result of this paper is a general Wei-type duality theorem for two Galois connections between finite subsets of $\mathbb {Z}$ , from which all the known Wei-type duality theorems can be recovered. As corollaries of our central result, we prove new Wei-type duality theorems for $w$ -demi-matroids defined over finite sets and $w$ -demi-polymatroids defined over modules with a composition series, which further allows us to unify and generalize all the known Wei-type duality theorems established for codes endowed with various metrics. [ABSTRACT FROM AUTHOR]

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $r\geq 3$ be a positive integer satisfying $\gcd (r,n)=1$ and $\gcd \big (r,q(q^{2}-1)\big)=1$. We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$. [ABSTRACT FROM AUTHOR]

Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in high-speed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over $\mathbb {F}_{M}$ of $M$ -ary Sidelnikov sequence of period $q-1$ using Hasse derivative, which implies $q=p^{m}$ , $m\geq 1$ and $M|(q-1)$. The $t$ th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for $M=2$ and 3 are obtained only with some additional restrictions on $q$. Furthermore, concrete illustrations for several families of these sequences, such as $q\equiv 1\pmod {2}$ and $q\equiv 1\pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2\times 3^{\lambda }+1 (1\leq \lambda \leq 20)$ , the exact linear complexities over $\mathbb {F}_{3}$ of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods. [ABSTRACT FROM AUTHOR]

The analysis of over-parameterized neural networks has drawn significant attention in recent years. It was shown that such systems behave like convex systems under various restricted settings, such as for two-layer neural networks, and when learning is only restricted locally in the so-called neural tangent kernel space around specialized initializations. However, there is a lack of powerful theoretical techniques that can analyze fully trained deep neural networks under general conditions. This paper considers this fundamental problem by investigating such overparameterized deep neural networks when fully trained. Specifically, we characterize a deep neural network by its features’ distributions and propose a metric to intuitively measure the usefulness of feature representations. Under certain regularizers that bounds the metric, we show deep neural networks can be reformulated as a convex optimization and the system can guarantee effective feature representations in terms of the metric. Our new analysis is more consistent with empirical observations that deep neural networks are capable of learning efficient feature representations. Empirical studies confirm that predictions of our theory are consistent with results observed in practice. [ABSTRACT FROM AUTHOR]

Traditional multi-armed bandit (MAB) formulations usually make certain assumptions about the underlying arms’ distributions, such as bounds on the support or their tail behaviour. Moreover, such parametric information is usually ‘baked’ into the algorithms. In this paper, we show that specialized algorithms that exploit such parametric information are prone to inconsistent learning performance when the parameter is misspecified. Our key contributions are twofold: (i) We establish fundamental performance limits of statistically robust MAB algorithms under the fixed-budget pure exploration setting, and (ii) We propose two classes of algorithms that are asymptotically near-optimal. Additionally, we consider a risk-aware criterion for best arm identification, where the objective associated with each arm is a linear combination of the mean and the conditional value at risk (CVaR). Throughout, we make a very mild ‘bounded moment’ assumption, which lets us work with both light-tailed and heavy-tailed distributions within a unified framework. [ABSTRACT FROM AUTHOR]

This paper presents a new approach, called perturb-max, for high-dimensional statistical inference in graphical models that is based on applying random perturbations followed by optimization. This framework injects randomness into maximum a-posteriori (MAP) predictors by randomly perturbing the potential function for the input. A classic result from extreme value statistics asserts that perturb-max operations generate unbiased samples from the Gibbs distribution using high-dimensional perturbations. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. However, when the perturbations are of low dimension, sampling the perturb-max prediction is as efficient as MAP optimization. This paper shows that the expected value of perturb-max inference with low dimensional perturbations can be used sequentially to generate unbiased samples from the Gibbs distribution. Furthermore the expected value of the maximal perturbations is a natural bound on the entropy of such perturb-max models. A measure concentration result for perturb-max values shows that the deviation of their sampled average from its expectation decays exponentially in the number of samples, allowing effective approximation of the expectation. [ABSTRACT FROM AUTHOR]

Motivated by systems, where the information is represented by a graph such as neural networks, associative memories, and distributed systems. In this paper, we present a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of undirected or directed complete graphs, and a code over graphs is a set of graphs. A node failure is the event, where all edges in the neighborhood of the erased node have been erased. We say that a code over graphs can tolerate $\rho $ node failures, if it can correct the erased edges of any $\rho $ failed nodes in the graph. While the construction of optimal codes over graphs can be easily accomplished by MDS codes, their field size has to be at least ${\mathcal{ O}}(n^{2})$ , when $n$ is the number of nodes in the graph. In this paper, we present several constructions of codes over graphs with smaller field size. To accomplish this task, we use constructions of product codes and rank metric codes. Furthermore, we present optimal codes over graphs correcting two node failures over the binary field, when the number of nodes in the graph is a prime number. Last, we also provide upper bound on the number of nodes for optimal codes. [ABSTRACT FROM AUTHOR]

This paper studies the continuous-time Poisson channel whose dark current is random and may change for every $\tau $ -second time interval, where the actual values of the dark current are known to the transmitter as channel-state information (CSI). In the limit where $\tau $ tends to zero, the capacity gain provided by both causal and noncausal CSI is shown to vanish linearly with $\tau $ , so CSI at the transmitter provides almost no capacity improvement. The paper also considers a related problem of the state-dependent very noisy channel. In the very noisy limit, the capacity gain provided by noncausal CSI is shown to be the same as that provided by causal CSI. [ABSTRACT FROM AUTHOR]

Modern communication and computation systems often consist of large networks of unreliable nodes. Still, it is well known that such systems can provide aggregate reliability via redundancy. While duplication may increase the load on a system, it can lead to significant performance improvement when combined with the judicious management of extra system resources. Prime examples of this abstract paradigm include multi-path routing across communication networks, content access from multiple caches in delivery networks, and master/slave computations on compute clusters. Several recent contributions in the area establish bounds on the performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this paper introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and a class of symmetric redundancy schemes, under the assumption of Poisson arrivals, exponential service-rates, and fork-join scheduling policy. The proposed approach can be employed to efficiently approximate the latency distribution of a queueing system at equilibrium. Various metrics can subsequently be derived for this system, including the mean and variance of the sojourn time, and the tail decay rate of the stationary distribution. This paper also establishes the stability region in terms of arrival rates for redundant systems with certain symmetries. Finally, it offers selection guidelines for design parameters to provide latency guarantees based on the proposed approximations. Findings are substantiated by numerical results. [ABSTRACT FROM AUTHOR]

We investigate the list decodability of symbol-pair codes in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric. [ABSTRACT FROM AUTHOR]

This paper derives upper and lower bounds on the secrecy capacity-memory tradeoff of a wiretap erasure broadcast channel (BC) with ${\mathsf{K}}_{w} $ weak receivers and ${\mathsf {K}}_{s} $ strong receivers, where weak receivers and strong receivers have the same erasure probabilities and cache sizes, respectively. The lower bounds are achieved by the schemes that meticulously combine joint cache-channel coding with wiretap coding and key-aided one-time pads. The presented upper bound holds more generally for arbitrary degraded BCs and arbitrary cache sizes. When only weak receivers have cache memories, upper and lower bounds coincide for small and large cache memories, thus providing the exact secrecy capacity-memory tradeoff for this setup. The derived bounds further allow us to conclude that the secrecy capacity is positive even when the eavesdropper is stronger than all the legitimate receivers with cache memories. Moreover, they show that the secrecy capacity-memory tradeoff can be significantly smaller than its non-secure counterpart, but it grows much faster when cache memories are small. This paper also presents a lower bound on the global secrecy capacity-memory tradeoff where one is allowed to optimize the cache assignment subject to a total cache budget. It is close to the best known lower bound without secrecy constraint. For small total cache budget, the global secrecy capacity-memory tradeoff is achieved by assigning all the available cache memory uniformly over all the receivers if the eavesdropper is stronger than all the legitimate receivers, and it is achieved by assigning the cache memory uniformly only over the weak receivers if the eavesdropper is weaker than the strong receivers. [ABSTRACT FROM AUTHOR]

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the channel impulse response. The mismatch capacity is the highest achievable rate for a given decoding rule. The existing achievable rates for channels and decoding metrics with memory (as in our model) are currently available only in the form of multi-letter expressions that cannot be calculated. Consequently, they provide little insight on the mismatch problem. In this paper, we derive the computable formulas of achievable rates and discuss some implications of our results. Our achievable rates are based on two ensembles: the ensemble of codewords generated by an autoregressive process and the ensemble of codewords drawn uniformly over a “type class” of real-valued sequences. We provide a few numerical results of our achievable rates, as functions of the mismatched ISI parameters. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper. [ABSTRACT FROM AUTHOR]

In the $q$ -ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf {x} =(x_{1},\ldots,x_{n}) \in \{0,1,\ldots,q-1\}^{n}$ symbol-by-symbol via a channel limited to at most $pn$ errors and $p^{*} n$ erasures. The channel is “online” in the sense that at the $i$ th step of communication the channel decides whether to corrupt the $i$ th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_{1},\ldots,x_{i})$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword $\mathbf {x}$. In this paper, we study the capacity of $q$ -ary online channels for a combined corruption model, in which the channel may impose at most $pn$ errors and at most $p^{*} n$ erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of $q,p$ , and $p^{*}$. [ABSTRACT FROM AUTHOR]

Given two discrete random variables $X$ and $Y$ , with probability distributions $p=(p_{1}, \ldots , p_{n})$ and $q=(q_{1}, \ldots , q_{m})$ , respectively, let us denote by ${\mathcal{ C}}(p, q)$ the set of all couplings of $p$ and $q$ , that is, the set of all bivariate probability distributions that have $p$ and $q$ as marginals. In this paper, we study the problem of finding a joint probability distribution in ${\mathcal{ C}}(p, q)$ of minimum entropy (equivalently, a coupling that maximizes the mutual information between $X$ and $Y$), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in ${\mathcal{ C}}(p, q)$ with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary $k\geq {2}$ discrete random variables $X_{1}, \ldots , X_{k}$ , consistent with the known $k$ marginal distributions of the individual random variables $X_{1}, \ldots , X_{k}$. In this case, our algorithm has an additive gap of at most $\log k$ from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy. [ABSTRACT FROM AUTHOR]

We consider an $\ell _{2}$ -regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty $ , $m/n \rightarrow \delta $ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals, the algorithm can perform accurate recovery with only $m = (({64}/{\pi ^{2}})-4)n \approx 2.5n$ measurements. Also, we provide a sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: 1) adding $\ell _{2}$ regularization to the non-convex loss function can be beneficial and 2) spectral initialization has a marginal impact on the performance of the algorithm. The sharp analyses, in this paper, not only enable us to compare the performance of our method with other phase recovery schemes but also shed light on designing better iterative algorithms for other non-convex optimization problems. [ABSTRACT FROM AUTHOR]

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are not only able to enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non-achievable, but whether it is asymptotically achievable or not remains open. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are a class of erasure-correcting array codes that combine local correction of the rows with global correction of the array. An $\boldsymbol {m}\times \boldsymbol {n}$ array code is called an $(\boldsymbol {r};\boldsymbol {s})$ PMDS code if each row belongs to an ${[}\boldsymbol {n},\boldsymbol {n}-\boldsymbol {r}, \boldsymbol {r}+\textbf {1}{]}$ MDS code and the code can correct erasure patterns consisting of $\boldsymbol {r}$ erasures in each row together with $\boldsymbol {s}$ more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates $(\boldsymbol {r};\boldsymbol {s})$ PMDS codes for all $\boldsymbol {r}$ and $\boldsymbol {s}$ , its field size is exponentially large. In this paper, a family of PMDS codes with field size ${\mathcal{ O}}\left ({\max \{\boldsymbol {m},\boldsymbol {n}^{\boldsymbol {r}+\boldsymbol {s}}\}^{\boldsymbol {s}} }\right)$ is presented for the case where $\boldsymbol {r}= {\mathcal{ O}}(1), \boldsymbol {s}= {\mathcal{ O}}(1)$. [ABSTRACT FROM AUTHOR]

Sparse superposition codes, or sparse regression codes, are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviation bound on the probability of an AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(\log n)^{2T}$ , where $T$ , the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity. [ABSTRACT FROM AUTHOR]

This paper considers the fundamental limit of random linear estimation for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of recovering an unknown but structured signal ${x}\in \mathbb {R} ^{n}$ from $m$ -quadratic measurements of the form ${y}_{r}= \left |{\langle {a}_{r}, {x}\rangle }\right |^{{2}}$ for ${r}={1},{2},\ldots, {m}$. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (${m} < < {n}$). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove the projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any closed constraint set (convex or non-convex) providing convergence guarantees to the global optimum even when the objective function and constraint set are nonconvex. Furthermore, these results hold with a number of measurements that are only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in this paper. In this paper, we utilize and further develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. [ABSTRACT FROM AUTHOR]

Vector autoregressive models characterize a variety of time series in which linear combinations of current and past observations can be used to accurately predict future observations. For instance, each element of an observation vector could correspond to a different node in a network, and the parameters of an autoregressive model would correspond to the impact of the network structure on the time series evolution. Often, these models are used successfully in practice to learn the structure of social, epidemiological, financial, or biological neural networks. However, little is known about statistical guarantees on the estimates of such models in non-Gaussian settings. This paper addresses the inference of the autoregressive parameters and associated network structure within a generalized linear model framework that includes Poisson and Bernoulli autoregressive processes. At the heart of this analysis is a sparsity-regularized maximum likelihood estimator. While sparsity-regularization is well-studied in the statistics and machine learning communities, those analysis methods cannot be applied to autoregressive generalized linear models because of the correlations and potential heteroscedasticity inherent in the observations. Sample complexity bounds are derived using a combination of martingale concentration inequalities and modern empirical process techniques for dependent random variables. These bounds, which are supported by several simulation studies, characterize the impact of various network parameters on the estimator performance. [ABSTRACT FROM AUTHOR]

This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois field coefficients of a non-binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois field varying from GF (64) up to GF (1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. [ABSTRACT FROM AUTHOR]

We study the first- and second-order asymptotics of covert communication over binary-input discrete memoryless channels for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the number of bits that can be reliably transmitted with a maximum probability of error less than $\epsilon $ and a relative entropy less than $\delta $. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish the exact first-order asymptotics and bound the second-order asymptotics. Pulse position modulation achieves the optimal first-order asymptotics for all three metrics, as well as the optimal second-order asymptotics for relative entropy. The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of covert communications. The main technical contribution underlying our results is a detailed expurgation argument to show the existence of a code satisfying the reliability and covertness criteria. [ABSTRACT FROM AUTHOR]

Over the past decade, the bulk of wireless traffic has shifted from speech to content. This shift creates the opportunity to cache part of the content in memories closer to the end users, for example in base stations. Most previous paper focuses on the reduction of load in the backhaul and core networks due to caching, i.e., on the benefits caching offers for the wireline communication link between the origin servers and the caches. In this paper, we are instead interested in the benefits caching can offer for the wireless communication link between the caches and the end users. To quantify the gains of caching for this wireless link, we consider an interference channel in which each transmitter is equipped with an isolated cache memory. Communication takes place in two phases, a content placement phase followed by a content delivery phase. The objective is to design both the placement and the delivery phases to maximize the rate in the delivery phase in response to any possible user demands. Focusing on the three-user case, we show that through careful joint design of these phases, we can reap three distinct benefits from caching: a load balancing gain, an interference cancellation gain, and an interference alignment gain. In our proposed scheme, load balancing is achieved through a specific file splitting and placement, producing a particular pattern of content overlap at the caches. This overlap allows to implement interference cancellation. Furthermore, it allows us to create several virtual transmitters, each transmitting a part of the requested content, which increases interference-alignment possibilities. [ABSTRACT FROM AUTHOR]

In this paper, we propose a lattice-based robust distributed source coding system for two correlated sources and provide a detailed performance analysis under the high resolution assumption. It is shown, among other things, that, in the asymptotic regime where: 1) the side distortion approaches 0 and 2) the ratio between the central and side distortions approaches 0, our scheme is capable of achieving the information-theoretic limit of quadratic multiple description coding when the two sources are identical, whereas a variant of the random coding scheme by Chen and Berger with Gaussian codes has a performance loss of 0.5 bits relative to this limit. [ABSTRACT FROM AUTHOR]