Search

The action of a noise operator on a code transforms it into a distribution on the respective space. Some common examples from information theory include Bernoulli noise acting on a code in the Hamming space and Gaussian noise acting on a lattice in the Euclidean space. We aim to characterize the cases when the output distribution is close to the uniform distribution on the space, as measured by the Rényi divergence of order α ∈ (1 , ∞ ] . A version of this question is known as the channel resolvability problem in information theory, and it has implications for security guarantees in wiretap channels, error correction, discrepancy, worst-to-average case complexity reductions, and many other problems. Our work quantifies the requirements for asymptotic uniformity (perfect smoothing) and identifies explicit code families that achieve it under the action of the Bernoulli and ball noise operators on the code. We derive expressions for the minimum rate of codes required to attain asymptotically perfect smoothing. In proving our results, we leverage recent results from harmonic analysis of functions on the Hamming space. Another result pertains to the use of code families in Wyner's transmission scheme on the binary wiretap channel. We identify explicit families that guarantee strong secrecy when applied in this scheme, showing that nested Reed–Muller codes can transmit messages reliably and securely over a binary symmetric wiretap channel with a positive rate. Finally, we establish a connection between smoothing and error correction in the binary symmetric channel. [ABSTRACT FROM AUTHOR]

We consider a general fingerprinting problem of digital data under which coalitions of users can alter or erase some bits in their copies in order to create an illegal copy. Each user is assigned a fingerprint which is a word in a fingerprinting code of size M (the total number of users) and length n. We present binary fingerprinting codes secure against size-t coalitions which enable the distributor (decoder) to recover at least one of the users from the coalition with probability of error exp(-[OMEGA](n)) for M = exp([OMEGA](n)). This is an improvement over the best known schemes that provide the error probability no better than exp(-[OMEGA]([n.sup.1/2])) and for this probability support at most exp(O([n.sup.1/2])) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n) = polylog(M), improving over the best previously known complexity of [OMEGA](M). For the case t = 2, we construct codes of exponential size with even stronger performance, namely, for which the distributor can either recover both users from the coalition with probability 1 - exp([OMEGA](n)), or identify one traitor with probability 1. Index Terms--Concatenated codes, fingerprinting problem, identification error, list decoding, polynomial-time decoding, separating codes.

Recently Reed-Solomon (RS) codes were shown to possess a repair scheme that supports repair of failed nodes with optimal repair bandwidth. In this paper, we extend this result in two directions. First, we propose a new repair scheme for the RS codes constructed in [Tamo-Ye-Barg, IEEE Transactions on Information Theory, vol. 65, May 2019] and show that repair is robust to erroneous information provided by the helper nodes while maintaining the optimal repair bandwidth. Second, we construct a new family of RS codes with optimal access for the repair of any single failed node. We also show that the constructed codes can accommodate both features, supporting optimal-access repair with optimal error-correction capability. Going beyond RS codes, we also prove that any scalar MDS code with repair bandwidth attaining the cutset bound affords a repair scheme with optimal access property. [ABSTRACT FROM AUTHOR]

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein ( , 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage. [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]

An (n,k,l) maximum distance separable (MDS) array code of length n , dimension k=n-r , and sub-packetization l is formed of l\times n matrices over a finite field F , with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of d\le n-1 surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with . In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any n and r , we presented an explicit construction of optimal-access MDS codes with sub-packetization . In this paper, we take up the question of reducing the sub-packetization value l to make it to approach the lower bound. We construct an explicit family of optimal-access codes with l=r^\lceil n/r\rceil , which differs from the optimal value by at most a factor of r^2 . These codes can be constructed over any finite field $F$ as long as $|F|\ge r\lceil n/r\rceil $ , and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access. In this variation, we assume that the set of $n=sm$ nodes is partitioned into $m$ repair groups of size $s$ , and require that the amount of accessed data for repair is the smallest possible whenever the $d=s+k-1$ helper nodes include all the other $s-1$ nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field $F$ of size $|F|\ge n$ , and also afford low-complexity encoding and decoding procedures. [ABSTRACT FROM PUBLISHER]

The minimum distance of some families of expander codes is studied, as well as some related families of codes defined on bipartite graphs. The weight spectrum and the minimum distance of a random ensemble of such codes are computed and it is shown that it sometimes meets the Gilbert-Varshamov (GV) bound. A lower bound on the minimum distances of constructive families of expander codes is derived. The relative minimum distance of the expander code is shown to exceed the product bound, i.e., the quantity δ0δ1 where δ0 and δ1 are the minimum relative distances of the constituent codes. As a consequence of this, a polynomially constructible family of expander codes is obtained whose relative distance exceeds the Zyablov bound on the distance of serial concatenations. [ABSTRACT FROM AUTHOR]

We derive Improved bounds on the error and erasure rate for spherical codes and for binary linear codes under Forney's erasure/list decoding scheme and prove some related results. [ABSTRACT FROM AUTHOR]

We extend a low-rate improvement of the random coding bound on the reliability of a classical discrete memoryless channel (DMC) to its quantum counterpart. The key observation that we make is that the problem of bounding below the error exponent for a quantum channel relying on the class of stabilizer codes is equivalent to the problem of deriving error exponents for a certain symmetric classical channel. [ABSTRACT FROM AUTHOR]

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x1, ... , xt if yi ε {xi1 , ... , xit} for all i = 1, ... , n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We prove that for any t ≤ q - 1 there exist sequences of such codes with asymptotically nonvanishing rate. [ABSTRACT FROM AUTHOR]

Presents a correction to the article "Bounds on Packings of Spheres in the Grassmann Manifold," that was previously published in the June 2005 issue of "IEEE Transactions on Information Theory."