Search

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. [ABSTRACT FROM AUTHOR]

This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters $(n,k,d,r,\delta )$ of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters $(n,k,d,r,\delta )$ and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

This paper aims to develop the insights into Bayesian truth serum (BTS) mechanism by postulating a sequence of seven natural conditions reminiscent of axioms in information theory. The condition that reduces a larger family of mechanisms to BTS is additivity, akin to the axiomatic development of entropy. The seven conditions identify BTS as the unique scoring rule for ranking respondents in situations in which respondents are asked to choose an alternative from a finite set and provide predictions of their peers’ propensities to choose, for finite or infinite sets of respondents. [ABSTRACT FROM AUTHOR]

This paper studies a two-user state-dependent Gaussian multiple-access channel (MAC) with state noncausally known at one encoder. Two scenarios are considered: 1) each user wishes to communicate an independent message to the common receiver; and 2) the two encoders send a common message to the receiver and the non-cognitive encoder (i.e., the encoder that does not know the state) sends an independent individual message (this model is also known as the MAC with degraded message sets). For both scenarios, new outer bounds on the capacity region are derived, which improve uniformly over the best known outer bounds. In the first scenario, the two corner points of the capacity region as well as the sum rate capacity are established, and it is shown that a single-letter solution is adequate to achieve both the corner points and the sum rate capacity. Furthermore, the full capacity region is characterized in situations in which the sum rate capacity is equal to the capacity of the helper problem. The proof exploits the optimal-transportation idea of Polyanskiy and Wu (which was used previously to establish an outer bound on the capacity region of the interference channel) and the worst case Gaussian noise result for the case in which the input and the noise are dependent. [ABSTRACT FROM AUTHOR]

As an optimal combinatorial object, zero-difference balanced (ZDB) functions introduced by Ding in 2008, are a generalization of the well-known perfect nonlinear functions. ZDB functions have received much attention in recent years due to its important applications in coding theory and sequence design. One objective of this paper is to present a construction of ZDB functions based on a kind of generalized cyclotomy. It generates ZDB functions over cyclic group with new parameters which can not be produced by earlier constructions. Another objective of this paper is to employ these ZDB functions to obtain at the same time: 1) optimal constant-composition codes; 2) perfect difference systems of sets; and 3) optimal frequency-hopping sequences, all with new parameters. [ABSTRACT FROM PUBLISHER]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

In this paper, we examine an input-constrained erasure channel and we characterize the asymptotics of its capacity when the erasure rate is low. More specifically, for a general memoryless erasure channel with its input supported on an irreducible finite-type constraint, we derive partial asymptotics of its capacity, using some series expansion type formula of its mutual information rate; and for a binary erasure channel with its first-order Markovian input supported on the $(1, \infty )$ -RLL constraint based on the concavity of its mutual information rate with respect to some parameterization of the input, we numerically evaluate its first-order Markov capacity and further derive its full asymptotics. The asymptotics obtained in this paper, when compared with the recently derived feedback capacity for a binary erasure channel with the same input constraint, enable us to draw the conclusion that feedback may increase the capacity of an input-constrained channel, even if the channel is memoryless. [ABSTRACT FROM PUBLISHER]

Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences. [ABSTRACT FROM AUTHOR]

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

In 2010, Silva et al. studied certain classes of finite-field matrix channels in order to model random linear network coding where exactly $t$ random errors are introduced. In this paper, we consider a generalization of these matrix channels where the number of errors is not required to be constant, indeed the number of errors may follow any distribution. We show that a capacity-achieving input distribution can always be taken to have a very restricted form (the distribution should be uniform given the rank of the input matrix). This result complements, and is inspired by a paper of Nobrega et al., which establishes a similar result for a class of matrix channels that model network coding with link erasures. Our result shows that the capacity of our channels can be expressed as maximization over probability distributions on the set of possible ranks of input matrices: a set of linear rather than exponential size. [ABSTRACT FROM AUTHOR]

Motivated by the error behavior in the DNA storage channel, in this paper, we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. Levenshtein considered the case in which all the channels have the same behavior, and we generalize this model and assume that the channels are not identical. Thus, different channels may cause different maximum numbers of errors. For example, we assume that there are N channels, which cause at most t1 or t2 errors, where t1 < t2, and the number of channels with at most t1 errors is at least [pN], for some fixed 0 < p < 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case. A different problem we study in this paper is where the number of channels is fixed, and the question is finding the minimum distance d that provides exact reconstruction. We study these problems and show how to apply them for the cases of substitutions and transpositions. [ABSTRACT FROM AUTHOR]

Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, $q$ -ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by $q$. Recently, it was shown through extension of construction by Tamo and Barg that length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, $q$ -ary optimal locally repairable codes could have length bigger than $q+1$. Thus, it becomes an interesting and challenging problem to construct $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of $q$ -ary optimal locally repairable codes of length up to $q+2\sqrt {q}$. It turns out that locality of our codes can be as big as 23 and distance can be linear in length. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

Using some recent results on asymptotically equivalent sequences of matrices, we present in this paper, a new derivation of the capacity formula given by Brandenburg and Wyner for a discrete-time Gaussian multiple-input-multiple-output channel with memory. In this paper, we tackle not only the case considered by them, where the number of channel inputs and the number of channel outputs are the same, but also when both numbers are different. [ABSTRACT FROM AUTHOR]

In addition to their applications in data storage, communications systems, and consumer electronics, linear complementary dual (LCD) codes—a class of linear codes—have been employed in cryptography recently. LCD cyclic codes were referred to as reversible cyclic codes in the literature. The objective of this paper is to construct several families of reversible cyclic codes over finite fields and analyze their parameters. The LCD cyclic codes presented in this paper have very good parameters in general, and contain many optimal codes. A well rounded treatment of reversible cyclic codes is also given in this paper. [ABSTRACT FROM PUBLISHER]

This paper studies codes that correct a burst of deletions or insertions. Namely, a code will be called a $b$ -burst-deletion/insertion-correcting code if it can correct a burst of deletions/insertions of any $b$ consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically $\log (n)+b-1$ , the redundancy of the best code construction by Cheng et al. is $b(\log (n/b+1))$ . In this paper, we close on this gap and provide codes with redundancy at most $\log (n) + (b-1)\log (\log (n)) +b -\log (b)$ . We first show that the models of insertions and deletions are equivalent and thus it is enough to study codes correcting a burst of deletions. We then derive a non-asymptotic upper bound on the size of $b$ -burst-deletion-correcting codes and extend the burst deletion model to two more cases: 1) a deletion burst of at most $b$ consecutive bits and 2) a deletion burst of size at most $b$ (not necessarily consecutive). We extend our code construction for the first case and study the second case for $b=3,4$ . [ABSTRACT FROM PUBLISHER]

This paper considers a state dependent broadcast channel with one transmitter, Alice, and two receivers, Bob and Eve. The problem is to effectively convey (“amplify”) the channel state sequence to Bob while “masking” it from Eve. The extent to which the state sequence cannot be masked from Eve is referred to as leakage. This can be viewed as a secrecy problem, where we desire that the channel state itself be minimally leaked to Eve while being communicated to Bob. This paper is aimed at characterizing the tradeoff region between amplification and leakage rates for such a system. An achievable coding scheme is presented, wherein the transmitter transmits a partial state information over the channel to facilitate the amplification process. For the case when Bob observes a stronger signal than Eve, the achievable coding scheme is enhanced with secure refinement. Outer bounds on the tradeoff region are also derived, and used in characterizing some special case results. In particular, the optimal amplification-leakage rate difference, called as differential amplification capacity, is characterized for the reversely degraded discrete memoryless channel, the degraded binary, and the degraded Gaussian channels. In addition, for the degraded Gaussian model, the extremal corner points of the tradeoff region are characterized, and the gap between the outer bound and achievable rate-regions is shown to be less than half a bit for a wide set of channel parameters. [ABSTRACT FROM PUBLISHER]

Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the method of constructing two-weight and three-weight linear codes of Ding et al. and Zhou et al. to general weakly regular bent functions and determines the weight distributions of these linear codes. It solves an open problem proposed by Ding et al. Furthermore, this paper constructs new linear codes with two or three weights and presents their weight distributions. They contain some optimal codes meeting certain bound on linear codes. [ABSTRACT FROM AUTHOR]

Reed–Muller codes belong to the family of affine-invariant codes. As such codes, they have a defining set that determines them uniquely, and they are extensions of cyclic group codes. In this paper, we identify those cyclic codes with multidimensional abelian codes and we use the techniques introduced by Bernal and Simón to construct information sets for them from their defining set. For first- and second-order Reed–Muller codes, we describe a direct method to construct information sets in terms of their basic parameters. [ABSTRACT FROM AUTHOR]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict avoiding codes. In this paper, we prove some nonexistence results for nonsingular perfect splitter sets. We also give some necessary conditions for the existence of purely singular perfect splitter sets. Finally, we apply these results to purely singular perfect $B[-1,k](m)$ and $B[-2,k](m)$ sets for small $k$. In particular, we solve completely the problems left by Schwartz (European J. Combin., vol. 36, pp.130–142, Feb. 2014). [ABSTRACT FROM AUTHOR]

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results. [ABSTRACT FROM AUTHOR]

Linear complementary dual (LCD) codes are a class of linear codes introduced by Massey in 1964. LCD codes have been extensively studied in literature recently. In addition to their applications in data storage, communications systems, and consumer electronics, LCD codes have been employed in cryptography. More specifically, it has been shown that LCD codes can also help improve the security of the information processed by sensitive devices, especially against so-called side-channel attacks (SCA) and fault non-invasive attacks. In this paper, we are interested in the construction of particular algebraic geometry LCD codes which could be good candidates to be resistant against SCA. We firstly provide a construction scheme for obtaining LCD codes from any algebraic curve. Then, some explicit LCD codes from elliptic curves are presented. Maximum distance separable (MDS) codes are of the most importance in coding theory due to their theoretical significance and practical interests. In this paper, all the constructed LCD codes from elliptic curves are MDS or almost MDS. Some infinite classes of LCD codes from elliptic curves are optimal due to the Griesmer bound. Finally, we also derive some explicit LCD codes from hyperelliptic curves and Hermitian curves. [ABSTRACT FROM AUTHOR]

A code is said to be an $r$ -local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most r$ other coordinates. When some of the r$ coordinates are also erased, the r$ -local LRC cannot accomplish the local repair, which leads to the concept of (r,\delta)$ -locality. A q is said to have (r, \delta)$ -locality ( \delta \ge 2$ ) if for each coordinate i with support containing $i$ , whose length is at most $r + \delta - 1$ , and whose minimum distance is at least $\delta$ . The $(r, \delta)$ -LRC can tolerate $\delta -1$ erasures in every local code (i.e., punctured subcode), which degenerates to an $r$ -local LRC when $\delta =2$ . A $q$ -ary $(r,\delta)$ LRC is called optimal if it meets the singleton-like bound for $(r,\delta)$ -LRCs. A class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q-1$ were constructed by Tamo, Barg, Goparaju, and Calderbank based on the $q$ -ary Reed-Solomon codes. In this paper, we construct a class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with length $n\mid q-1$ , which generalizes the results of Tamo et al. Moreover, we construct a new class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q+1$ and a new class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with lengths $n\mid q+1$ . The constructed optimal LRCs with length $n=q+1$ have the best-known length for a given finite field with size $q$ when the minimum distance is larger than 4. [ABSTRACT FROM AUTHOR]

In this paper, we consider the maximum absolute value \Delta f in the autocorrelation spectrum (not considering the zero point) of a function f . In an even number of variables n , bent functions possess the highest nonlinearity with \Delta f = 0 . The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with \Delta f < 2^{n/2} . So far, there are only a few examples of such functions for n = 10, 14 , but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on n variables having absolute indicator strictly lesser than \delta n = 2^{n/2}-2^{(({n+6})/{4})} , nonlinearity strictly greater than \rho n = 2^{n-1} - 2^{n/2} + 2^{n/2-3} - 5\cdot 2^{(({n-2})/{4})} and algebraic degree n-1 , where n\equiv 2 \pmod 4 and n\geq 46 . While the bound n \geq 46 is required for proving the generic result, our construction starts from n = 18 and nonlinearity > 2^n-1 - 2^n/2 for n = 18, 22 , and 26. [ABSTRACT FROM PUBLISHER]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

The nonlinear complexity of a periodic sequence s is the length of the shortest feedback shift register that can generate s, and its value is upper bounded by the least period of s minus 1. In this paper, a recursive approach that generates all periodic sequences with maximum nonlinear complexity is presented, and the total number of such sequences is determined. The randomness properties of these sequences are also examined. [ABSTRACT FROM PUBLISHER]

Data centers play an important role in today’s Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N\subseteq V(G) be a set of nodes. A path system \mathcal P of G with respect to N consists of |N|(|N|-1) directed paths, one path to connect each of the source-destination node pairs in N . The global packing number of a path system , denoted by \Phi (G,N,\mathcal {P}) , is the minimum integer k to guarantee the existence of a mapping \phi :\mathcal P\to \1,2,\ldots, k\ , such that \phi (P)\neq \phi (\widehat P) if P and \widehat {P} have common arc(s). The global packing number of (G,N) , denoted by \Phi (G,N) , is defined to be the minimum \Phi (G,N,\mathcal {P}) among all possible path systems \mathcal {P} . In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (\text Tn,N) , where Tn denotes the topology of the n -ary fat-tree network, and $N$ is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links. [ABSTRACT FROM AUTHOR]

In this paper, we study linear encoding for a pair of correlated Gaussian sources transmitted over a two-user Gaussian broadcast channel in the presence of unit-delay noiseless feedback, abbreviated as the GBCF. Each pair of source samples is transmitted using a linear transmission scheme in a finite number of channel uses. We investigate three linear transmission schemes: A scheme based on the Ozarow–Leung (OL) code, a scheme based on the linear quadratic Gaussian (LQG) code of Ardestanizadeh et al., and a novel scheme derived in this paper using a dynamic programming (DP) approach. For the OL and LQG schemes we present lower and upper bounds on the minimal number of channel uses needed to achieve a target mean-square error (MSE) pair. For the LQG scheme in the symmetric setting, we identify the optimal scaling of the sources, which results in a significant improvement of its finite horizon performance, and, in addition, characterize the (exact) minimal number of channel uses required to achieve a target MSE. Finally, for the symmetric setting, we show that for any fixed and finite number of channel uses, the DP scheme achieves an MSE lower than the MSE achieved by either the LQG or the OL schemes. [ABSTRACT FROM AUTHOR]

A generalized Chinese remainder theorem (CRT) for multiple integers from residue sets has been studied recently, where the correspondence between the remainders and the integers in each residue set modulo several moduli is not known. A robust CRT has also been proposed lately to robustly reconstruct a single integer from its erroneous remainders. In this paper, we consider the reconstruction problem of two integers from their residue sets, where the remainders not only are out of order but also may have errors. We prove that two integers can be robustly reconstructed if their remainder errors are less than $M/8$ , where $M$ is the greatest common divisor of all the moduli. We also propose an efficient reconstruction algorithm. Finally, we present some simulations to verify the efficiency of the proposed algorithm. This paper is motivated from and has applications in the determination of multiple frequencies from multiple undersampled waveforms. [ABSTRACT FROM PUBLISHER]

In this paper we extend the notion of locally repairable codes to secret sharing schemes. The main problem that we consider is to find optimal ways to distribute the shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using the contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a passive eavesdropper that can observe some subsets of nodes. We provide a number of results related to such systems, including upper bounds and achievability results on the number of bits that can be securely stored with these constraints. In particular, we provide conditions under which a locally repairable code can be turned into a secret sharing scheme and extend the results of secure repairable storage to cooperative repair and storage on networks. In addition, we consider perfect secret sharing schemes over general access structures under locality constraints and give an example of a perfect secret sharing scheme that can have small locality. Finally, we provide a lower bound on the size of a share compared with the size of the secret that shows how locality affects the sizes of shares in a perfect scheme. [ABSTRACT FROM PUBLISHER]

Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function. [ABSTRACT FROM AUTHOR]

This paper presents the Bayes Fisher information measures, defined by the expected Fisher information under a distribution for the parameter, for the arithmetic, geometric, and generalized mixtures of two probability density functions. The Fisher information of the arithmetic mixture about the mixing parameter is related to chi-square divergence, Shannon entropy, and the Jensen–Shannon divergence. The Bayes Fisher measures of the three mixture models are related to the Kullback–Leibler, Jeffreys, Jensen–Shannon, Rényi, and Tsallis divergences. These measures indicate that the farther away are the components from each other, the more informative are data about the mixing parameter. We also unify three different relative entropy derivations of the geometric mixture scattered in statistics and physics literatures. Extensions of two of the formulations to the minimization of Tsallis divergence give the generalized mixture as the solution. [ABSTRACT FROM AUTHOR]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

We consider list decoding in the zero-rate regime for two cases—the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $\tau \in [{0,1}]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $\tau $ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $M\to \infty $ the maximal $\tau $ decreases to a well-known critical value $\tau _{L}$. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $\Theta (M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$. For $L=3$ , the rate is shown to be $\Theta (M^{-({2}/{3})})$. For the similar question about spherical codes, we prove the rate is $\Omega (M^{-1})$ and $O(M^{-({2L}/{L^{2}-L+2})})$. [ABSTRACT FROM AUTHOR]

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed–Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size $q$. Recently, it was proved through the extension of construction by Tamo and Barg that the length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al. Surprisingly, Barg et al. presented a few examples of $q$ -ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^{2}$. Very recently, it was further shown in the work of Li et al. that there exist $q$ -ary optimal locally repairable codes with the length bigger than $q+1$ and the distance proportional to $n$. Thus, it becomes an interesting and challenging problem to construct new families of $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen. [ABSTRACT FROM AUTHOR]

Compute-and-forward (CF) harnesses interference in wireless communications by exploiting structured coding. The key idea of CF is to compute integer combinations of code words from multiple source nodes, rather than to decode individual code words by treating others as noise. Compute-compress-and-forward (CCF) can further enhance the network performance by introducing compression operations at receivers. In this paper, we develop a more general compression framework, termed generalized CCF (GCCF), where the compression function involves the selection of message segments over finite fields. We show that GCCF achieves a broader compression rate region than CCF. We also compare our compression rate region with the fundamental Slepian–Wolf (SW) region. We show that GCCF is optimal in the sense of achieving the minimum total compression rate. We also establish the criteria under which GCCF achieves the SW region. In addition, we consider a two-hop relay network employing the GCCF scheme. We formulate a sum-rate maximization problem and develop an approximate algorithm to solve the problem. Numerical results are presented to demonstrate the performance superiority of GCCF over CCF and other schemes. [ABSTRACT FROM AUTHOR]

Pattern recognition based on a high-dimensional predictor is considered. A classifier is defined which is based on a Transformer encoder. The rate of convergence of the misclassification probability of the classifier towards the optimal misclassification probability is analyzed. It is shown that this classifier is able to circumvent the curse of dimensionality provided the a posteriori probability satisfies a suitable hierarchical composition model. Furthermore, the difference between the Transformer classifiers theoretically analyzed in this paper and the ones used in practice today is illustrated by means of classification problems in natural language processing. [ABSTRACT FROM AUTHOR]

For delay-limited communication over block-fading channels, the difference between the ergodic capacity and the maximum achievable expected rate for coding over a finite number of coherent blocks represents a fundamental measure of the penalty incurred by the delay constraint. This paper introduces a notion of worst-case expected-capacity loss. Focusing on the slow-fading scenario (one-block delay), the worst-case additive and multiplicative expected-capacity losses are precisely characterized for the point-to-point fading channel. Extension to the problem of writing on fading paper is also considered, where both the ergodic capacity and the additive expected-capacity loss over one-block delay are characterized to within one bit per channel use. [ABSTRACT FROM PUBLISHER]

In a memristor crossbar array, functioning as a memory array, a memristor is positioned on each row–column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this paper, we study the sneak path problem in crossbar arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are modeling the error channel induced by sneak paths, a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method, we match a constraint on the array content that guarantees sneak-path free readout, determine the resulting capacity, and provide an efficient encoder that achieves the capacity. [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

When transmitting information over a noisy channel, two approaches, dating back to Shannon’s work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$ -RLL tends to 1 as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems. [ABSTRACT FROM AUTHOR]

In an acyclic multicast network, it is well known that a linear network coding solution over GF( q ) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF( q ) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every \omega \geq 3 , there is a multicast network with source outdegree \omega linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF( q ) and over GF( q^m2 ) is not necessarily linearly solvable over GF( q^{m1 + m2} ); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size q_{\mathrm{ min}} for a linear solution over GF( q_{\mathrm{ min}} ) is lower bounded by \Theta (\sqrt T) , but not every larger field than GF( q\mathrm{ min} ) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network. [ABSTRACT FROM AUTHOR]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

We consider the minimax estimation problem of a discrete distribution with support size $k$ under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number $\epsilon $ measures the privacy level of a privatization scheme. For a given $\epsilon $ , we consider the problem of constructing optimal privatization schemes with $\epsilon $ -privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where $\epsilon $ is very close to 0, and in the low privacy regime where $e^{\epsilon }\approx k$ , respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when $1\ll e^{\epsilon } \ll k$. More concretely, we prove that when $3.8 < \epsilon <\ln (k/9) $ , our schemes reduce the expected estimation loss by 50% under $\ell _{2}^{2}$ metric and by 30% under $\ell _{1}$ metric over the existing schemes. We also prove a lower bound for the region $e^{\epsilon } \ll k$ , which implies that our schemes are order optimal in this regime. [ABSTRACT FROM AUTHOR]

This paper considers vector network coding solutions based on rank-metric codes and subspace codes. The main result of this paper is that vector solutions can significantly reduce the required alphabet size compared to the optimal scalar linear solution for the same multicast network. The multicast networks considered in this paper have one source with h messages, and the vector solution is over a field of size q with vectors of length t . For a given network, let the smallest field size for which the network has a scalar linear solution be , then the gap in the alphabet size between the vector solution and the scalar linear solution is defined to be q_{s}-q^{t} . In this contribution, the achieved gap is q^{(h-2)t^{2}/h + o(t)}$ for any q \geq 2$ and any even h \geq 4$ . If h \geq 5 . Previously, only a gap of size one had been shown for networks with a very large number of messages. These results imply the same gap of the alphabet size between the optimal scalar linear and some scalar nonlinear network coding solution for multicast networks. For three messages, we also show an advantage of vector network coding, while for two messages the problem remains open. Several networks are considered, all of them are generalizations and modifications of the well-known combination networks. The vector network codes that are used as solutions for those networks are based on subspace codes, particularly subspace codes obtained from rank-metric codes. Some of these codes form a new family of subspace codes, which poses a new research problem. [ABSTRACT FROM AUTHOR]

Finding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. This paper studies ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Unlike our previous work, which establishes deterministic (worst-case) sparsity bounds for ProSparse to succeed, this paper presents a probabilistic average-case analysis of the algorithm. Based on a generating-function approach, closed-form expressions for the exact success probabilities of ProSparse are given. The success probabilities are also analyzed in the high-dimensional regime. This asymptotic analysis characterizes a sharp phase transition phenomenon regarding the performance of the algorithm. [ABSTRACT FROM AUTHOR]

This paper quantifies the intuitive observation that adding noise reduces available information by means of nonlinear strong data processing inequalities. Consider the random variables W\to X\to Y forming a Markov chain, where Y = X + Z with X and Z real valued, independent and X -norm. It is shown that I(W; Y) \le FI(I(W;X)) with FI(t) < t whenever $t > 0$ , if and only if $Z$ has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings $(W, X)$ the mutual information $I(W; Y)$ is close to maximum possible. To that end we show that in order to saturate the channel, i.e., for $I(W; Y)$ to approach capacity, it is mandatory that $I(W; X)\to \infty $ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that postconvolution total variation distance bounds the preconvolution Kolmogorov–Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order optimal. For this case, simplified proofs are provided leveraging Gaussian-specific tools such as the connection between information and estimation (I-MMSE) and Talagrand’s information-transportation inequality. [ABSTRACT FROM PUBLISHER]

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length $L$ , which can be interpreted as the coherence time of the energy-arrival process. If L$ is a constant or grows sublinearly in the blocklength n$ , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability \varepsilon $ . The first-order term is known as the \varepsilon for any $\varepsilon $ less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$ , we obtain lower and upper bounds on the $\varepsilon $ -capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks. [ABSTRACT FROM PUBLISHER]