Search

We derive universal classical-quantum superposition coding and universal classical-quantum multiple access channel coding by using generalized packing lemmas for the type method. Using our classical-quantum universal superposition code, we establish the capacity region of a classical-quantum compound broadcast channel with degraded message sets. Our universal classical-quantum multiple access channel codes have two types of codes. One is a code with joint decoding and the other is a code with separate decoding. It is not so easy to construct a former code that universally achieves general points of the capacity region beyond corner points. First, we construct the latter code that universally achieves general points of the capacity region. Then, converting the latter code to the former coder, we construct the above desired code with the former type. [ABSTRACT FROM AUTHOR]

We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound. [ABSTRACT FROM AUTHOR]

Given a computable probability measure $P$ over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of $P$. In addition, given a binary predicate $\gamma $ , the length of the smallest program that computes a complete extension of $\gamma $ is less than the size of the domain of $\gamma $ plus the amount of information that $\gamma $ has with the halting sequence. [ABSTRACT FROM AUTHOR]

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters $[n,k,d]$ and the list size $L$. $L$ -MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes. [ABSTRACT FROM AUTHOR]

We consider the task of communicating a generic bivariate function of two classical correlated sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. We first propose a coding scheme based on asymptotically good algebraic structured codes, in particular, nested coset codes, and provide a set of sufficient conditions for the reconstruction of the function of the sources over a CQ-MAC. The proposed technique enables the decoder to recover the desired function without recovering the sources themselves. We further improve this by employing a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes. This coding scheme allows exploiting the symmetric structure common amongst the sources and also leverage the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources whose function can be reconstructed over any given CQ-MAC, and identify examples demonstrating the same. We provide these conditions in terms of single-letter quantum information-theoretic quantities. [ABSTRACT FROM AUTHOR]

Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $> 1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems. [ABSTRACT FROM AUTHOR]

Kim et al. (2021) gave a method to embed a given binary $[n,k]$ code $\mathcal {C}\,\,(k = 3, 4)$ into a self-orthogonal code of the shortest length which has the same dimension $k$ and minimum distance $d' \ge d(\mathcal {C})$. We extend this result by proposing a new method related to a special matrix, called the self-orthogonality matrix $SO_{k}$ , obtained by shortening a Reed-Muller code ${\mathcal R}(2,k)$. Using this approach, we can extend binary linear codes to many optimal self-orthogonal codes of dimensions 5 and 6. Furthermore, we partially disprove the conjecture (Kim et al. (2021)) by showing that if $31 \le n \le 256$ and $n\equiv 14,22,29 \pmod {31}$ , then there exist optimal $[n], [5]$ codes which are self-orthogonal. We also construct optimal self-orthogonal $[n], [6]$ codes when $41 \le n \le 256$ satisfies $n \ne 46, 54, 61$ and $n \equiv \!\!\!\!\!/~7, 14, 22, 29, 38, 45, 53, 60 \pmod {63}$. [ABSTRACT FROM AUTHOR]

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using $\tilde{\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}(n+g))$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell $ is the designed list size and $\mu $ is the smallest positive element in the Weierstrass semigroup at some chosen place; the “soft-O” notation $\tilde{\mathcal {O}} (\cdot)$ is similar to the “big-O” notation $\mathcal {O}(\cdot)$ , but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

Let $n=2m$. In 2020, Budaghyan, Helleseth and Kaleyski [IEEE TIT 66(11): 7081-7087, 2020] considered a family of quadrinomials over $\mathbb {F}_{2^{n}}$ of the form $x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot 2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}}$. They showed that two infinite classes of almost perfect nonlinear (APN) functions belong to this family when $\gcd (6,m)=1$. We observe that these two infinite classes of APN quadrinomials and the infinite class of APN polynomials from the Budaghyan-Carlet family belong to a more general family of polynomials over $\mathbb {F}_{2^{n}} $ with the form $f(x)=a{\mathrm{ Tr}}^{n}_{m}(F(x))+a^{2^{m}}{\mathrm{ Tr}}^{n}_{m}(G(x))$ , where $a \in \mathbb {F}_{2^{n}}\backslash \mathbb {F}_{2^{m}} $ , and both $F$ and $G$ are quadratic functions over $\mathbb {F}_{2^{n}}$. We characterize when $f(x) $ is APN. With the help of our characterization, letting $F(x)=bx^{2^{i}+1} $ and $G(x)=cx^{2^{s}+1}$ with $b, c\in \mathbb {F}_{2^{n}} $ , we obtain an infinite family of APN functions of the form $f(x) $ when ${\mathrm{ gcd}}(2,m)=1 $ and verify that for $n=10 $ two APN instances from this infinite family are CCZ-inequivalent to each other, and to any APN function over $\mathbb {F}_{2^{10}} $ from the previously known infinite families. [ABSTRACT FROM AUTHOR]

We study the problem of simulating a two-user multiple-access channel (MAC) over a multiple access network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links between each encoder and the decoder, and there is independent pairwise shared randomness between all the three possible pairs of nodes. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the two sources and the side information. We are interested in the rate tuples which permit this simulation. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). When the pairwise shared randomness between the encoders is absent, the setting reduces to a special case of MAC simulation using another MAC studied by Haddadpour et al. (2013). We establish that the presence of encoder shared randomness can strictly improve the communication rate requirements. We first show that the inner bound derived from Haddadpour et al. (2013) is tight when the sources at the encoders are conditionally independent given the side-information at the decoder. This result recovers the existing results on point-to-point channel simulation and function computation over such multi-terminal networks. We then explicitly compute the communication rate regions for an example both with and without the encoder shared randomness and demonstrate that its presence strictly reduces the communication rates. Inner and outer bounds for the general case are also obtained. [ABSTRACT FROM AUTHOR]

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads $N$ is fixed. Of significance, for the single-deletion channel, using $\log _{2}\log _{2} n +O(1)$ redundant bits, we designed a reconstruction code of length $n$ that reconstructs codewords from two distinct noisy reads (Cai et al., 2021). In this work, we show that $\log _{2}\log _{2} n -O(1)$ redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in $t$ -deletion channels (with $t \geqslant 2$) to uniquely reconstruct codewords from ${n^{t-1}}/{(t-1)!}+O\left ({n^{t-2}}\right)$ distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class of higher order constrained shifted VT code with $2\log _{2} n +o(\log _{2}(n))$ redundancy bits that can reconstruct any codeword from any $N \geqslant 5$ of its length- $(n-2)$ subsequences. [ABSTRACT FROM AUTHOR]

We prove that for $n$ sufficiently large, all perfect 3-hash linear codes in $\mathbb {F}_{3}^{n}$ must have dimension at most $\left ({\frac {1}{4}-\epsilon }\right)n$ for some absolute constant $\epsilon > 0$. [ABSTRACT FROM AUTHOR]

The DNA storage channel is considered, in which a codeword is comprised of $M$ unordered DNA molecules. At reading time, $N$ molecules are sampled with replacement, and then each molecule is sequenced. A coded-index concatenated-coding scheme is considered, in which the $m$ th molecule of the codeword is restricted to a subset of all possible molecules (an inner code), which is unique for each $m$. The decoder has low-complexity, and is based on first decoding each molecule separately (the inner code), and then decoding the sequence of molecules (an outer code). Only mild assumptions are made on the sequencing channel, in the form of the existence of an inner code and decoder with vanishing error. The error probability of a random code as well as an expurgated code is analyzed and shown to decay exponentially with $N$. This establishes the importance of increasing the coverage depth $N/M$ in order to obtain low error probability. [ABSTRACT FROM AUTHOR]

The design of decoding algorithms is a significant technological component in the development of fault-tolerant quantum computers. Often design of quantum decoders is inspired by classical decoding algorithms, but there are no general principles for building quantum decoders from classical decoders. Given any pair of classical codes, we can build a quantum code using the hypergraph product, yielding a hypergraph product code. Here we show we can also lift the decoders for these classical codes. That is, given oracle access to a minimum weight decoder for the relevant classical codes, the corresponding $[[n,k,d]]$ quantum code can be efficiently decoded for any error of weight smaller than $(d-1)/2$. The quantum decoder requires only $O(k)$ oracle calls to the classical decoder and $O(n^{2})$ classical resources. The lift and the correctness proof of the decoder have a purely algebraic nature that draws on the discovery of some novel homological invariants of the hypergraph product codespace. While the decoder works perfectly for adversarial errors, that is errors of weight up to half the code distance, it is not suitable for more realistic stochastic noise models and therefore can not be used to establish an error correcting threshold. [ABSTRACT FROM AUTHOR]

A class of self-dual quasi-abelian codes of index 2 over any finite field $F$ is introduced. By counting the number of such codes and the number of the codes in this class whose relative minimum weights are small, such codes are proved to be asymptotically good provided −1 is a square in $F$. Moreover, a class of self-orthogonal quasi-abelian codes of index 2 is defined; and such codes always exist. In a way similar to that for self-dual quasi-abelian codes of index 2, it is proved that these self-orthogonal quasi-abelian codes of index 2 are asymptotically good. [ABSTRACT FROM AUTHOR]

We present two lower bounds on sub-packetization level $\alpha $ of MSR codes with parameters $(n, k, d=n-1, \alpha)$ where $n$ is the block length, $d$ is the number of helper nodes contacted during single-node repair, $\alpha $ the sub-packetization level and $k\alpha $ the scalar dimension. The first bound we present is for any MSR code and is given by $\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by $\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the $\beta $ scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code. [ABSTRACT FROM AUTHOR]

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Sima et al. (ISIT 2020), we construct a family of binary single-deletion $s$ -substitution correcting codes with redundancy $(s+1) (2s+1)\log _{2} n+o(\log _{2} n)$ and encoding complexity $O(n^{2})$ , where $n$ is the blocklength of the code and $s\geq 1$. The construction can be viewed as a generalization of Smagloy et al.’s construction (ISIT 2020), and for the special case of $s=1$ , our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic $t$ -deletion $s$ -substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where $t\geq 1$ and $s\geq 1$. Specifically, our binary $t$ -deletion $s$ -substitution correcting codes of length $n$ have redundancy $(4t+3s)\log _{2}n+o(\log _{2}n)$ , whereas, for $q$ being a prime power, the redundancy of $q$ -ary $t$ -deletion $s$ -substitution codes is asymptotically $\left({4t+4s-1-\lfloor \frac {2s-1}{q}\rfloor }\right)\vphantom {{\lfloor \frac {2s-1}{q}\rfloor }_{j}}\log _{q} n + o(\log _{q}n)$ as $n\to \infty $. We also construct a family of binary systematic $t$ -deletion correcting codes (i.e., $s=0$) with redundancy $(4t-1)\log _{2} n+o(\log _{2} n)$. The proposed constructions improve upon the redundancy of the state-of-the-art constructions. [ABSTRACT FROM AUTHOR]

Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditional block codes and are thus especially appealing for delay sensitive applications. Existing works on streaming code performance either focused on the asymptotic error-exponent analyses, or on the optimal code construction under deterministic adversarial channel models. In contrast, this work analyzes the exact error probability of random linear streaming codes (RLSCs) in the large field size regime over the stochastic i.i.d. symbol erasure channel model. A closed-form expression of the error probability of large-field-size RLSCs is derived under, simultaneously, the finite memory length and decoding deadline constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40–48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2–10% delay reduction). [ABSTRACT FROM AUTHOR]

In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over $\mathbb {F}_{q}$ , for $q= {\mathrm {poly}}(1/\varepsilon)$ , that can efficiently decode from a $\delta $ fraction of insdel errors and have rate $(1-4\delta)/8-\varepsilon $. We also show that by allowing codes over $\mathbb {F}_{q^{2}}$ that are linear over $\mathbb {F}_{q}$ , we can improve the rate to $(1-\delta)/4-\varepsilon $ while not sacrificing efficiency. Using this latter result, we construct fully linear codes over $\mathbb {F}_{2}$ that can efficiently correct up to $\delta < 1/54$ fraction of deletions and have rate $R = (1-54\cdot \delta)/1216$. Cheng et al. (2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a $\delta < 1/400$ fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the half-Singleton bound [proved in Cheng et al. (2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound. [ABSTRACT FROM AUTHOR]

It is well known that independent (separate) encoding of $K$ correlated sources may incur some rate loss compared to joint encoding, even if the decoding is done jointly. This loss is particularly evident in the multiple descriptions problem, where it is the same source that is encoded in each description. We observe that under mild conditions about the source and distortion measure, the sum-rate of $K$ separately encoded individually good descriptions tends to the rate-distortion function of the joint decoder in the limit of vanishing small coding rates of the descriptions. Moreover, we then propose to successively encode the source into $K$ independent descriptions in each round in order to achieve a final distortion $D$ after $M$ rounds. We provide two examples – a Gaussian source with mean-squared error and an exponential source with one-sided error – for which the excess rate vanishes in the limit as the number of rounds $M$ goes to infinity, for any fixed $D$ and $K$. This result has an interesting interpretation for a multi-round variant of the multiple descriptions problem, where after each round the encoder gets a (block) feedback regarding which of the descriptions arrived: In the limit as the number of rounds $M$ goes to infinity (i.e., many incremental rounds), the total rate of received descriptions approaches the rate-distortion function. We provide theoretical and experimental evidence showing that this phenomenon is in fact more general than in the two examples above. [ABSTRACT FROM AUTHOR]

Trace reconstruction considers the task of recovering an unknown string $\mathbf {x}\in \{0,1\}^{n}$ given a number of independent “traces”, i.e., subsequences of $\mathbf {x}$ obtained by randomly and independently deleting every symbol of $\mathbf {x}$ with some probability $p$. The information-theoretic limit of the number of traces needed to recover a string of length $n$ is still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $\mathbf {x}$ and $\mathbf {y}$ and traces of one of them, which string is the source. The most-studied class of algorithms for the worst-case version of the problem are “mean-based” algorithms. These are a restricted class of distinguishers that only use the mean value of each coordinate on the given samples. In this work we study limitations of mean-based algorithms on strings at small Hamming or edit distance. We show that, on the one hand, distinguishing strings that are nearby in Hamming distance is “easy” for such distinguishers. On the other hand, we show that distinguishing strings that are nearby in edit distance is “hard” for mean-based algorithms. Along the way, we also describe a connection to the famous Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit hard-to-distinguish strings: namely such strings would imply explicit short solutions to the PTE problem, a well-known difficult problem in number theory. Furthermore, we show that the converse is also true, thus, finding explicit solutions to the PTE problem is equivalent to the problem of finding explicit strings that are hard-to-distinguish by mean-based algorithms. Our techniques rely on complex analysis arguments that involve careful trigonometric estimates, and algebraic techniques that include applications of Descartes’ rule of signs for polynomials over the reals. [ABSTRACT FROM AUTHOR]

The aim of this work is to study the structure and properties of the binary LCD codes having an automorphism of odd prime order and to present a method for their construction. [ABSTRACT FROM AUTHOR]

Model complexity plays an essential role in its selection, namely, by choosing a model that fits the data and is also succinct. Two-part codes and the minimum description length have been successful in delivering procedures to single out the best models, avoiding overfitting. In this work, we pursue this approach and complement it by performing further assumptions in the parameter space. Concretely, we assume that the parameter space is a smooth manifold, and by using tools of Riemannian geometry, we derive a sharper expression than the standard one given by the stochastic complexity, where the scalar curvature of the Fisher information metric plays a dominant role. Furthermore, we compute a sharper approximation to the capacity for exponential families and apply our results to derive optimal dimensional reduction in the context of principal component analysis. [ABSTRACT FROM AUTHOR]

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g., $L\in {[{8, 1024}]}$ , are adopted. Exemplary constructions with block lengths $N\in \{128,512\}$ outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean. [ABSTRACT FROM AUTHOR]

We define a new family of codes for symmetric classical-quantum channels and establish their optimality. To this end, we extend the classical notion of generalized perfect and quasi-perfect codes to channels defined over some finite dimensional complex Hilbert output space. The resulting optimality conditions depend on the channel considered and on an auxiliary state defined on the output space of the channel. For certain $N$ -qubit classical-quantum channels, we show that codes based on a generalization of Bell states are quasi-perfect and, therefore, they feature the smallest error probability among all codes of the same blocklength and cardinality. [ABSTRACT FROM AUTHOR]

We introduce quantum pin codes: a class of quantum CSS codes. Quantum pin codes are a generalization of quantum color codes and Reed-Muller codes and share a lot of their structure and properties. Pin codes have gauge operators, an unfolding procedure and their stabilizers form so-called $\ell $ -orthogonal spaces meaning that the joint overlap between any $\ell $ stabilizer elements is always even. This last feature makes them interesting for devising magic-state distillation protocols, for instance by using puncturing techniques. We study examples of these codes and their properties. [ABSTRACT FROM AUTHOR]

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas. [ABSTRACT FROM AUTHOR]

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log (n)$ bits in one sub-regime, and at most $\Omega ({n})$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping. [ABSTRACT FROM AUTHOR]

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support. [ABSTRACT FROM AUTHOR]

The traditional definition of Integrated Interleaved (II) codes generally assumes that the component nested codes are either Reed-Solomon (RS) or shortened Reed-Solomon codes. By taking general classes of codes, we present a recursive construction of Extended Integrated Interleaved (EII) codes into multiple layers, a problem that brought attention in literature for II codes. The multiple layer approach allows for a hierarchical scheme where each layer of the code provides for a different locality. In particular, we present the erasure-correcting capability of the new codes and we show that they are ideally suited as Locally Recoverable codes (LRC) due to their hierarchical locality and the small finite field required by the construction. Properties of the multiple layer EII codes, like their minimum distance and dimension, as well as their erasure decoding algorithms, parity-check matrices and performance analysis, are provided and illustrated with examples. Finally, we will observe that the parity-check matrices of high layer EII codes have low density. [ABSTRACT FROM AUTHOR]

We construct a family of $(n,k)$ convolutional codes with degree $\delta \in \{k,n-k\}$ that have a maximum distance profile. The field size required for our construction is $\Theta (n^{2\delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials. [ABSTRACT FROM AUTHOR]

While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum error-correcting codes, these bounds are not optimized to quantify the performance of quantum codes under the effect of arbitrary quantum channels that describe bespoke noise models. Herein, for any Kraus decomposition of any given quantum channel, we introduce corresponding quantum weight enumerators that naturally generalize the Shor-Laflamme quantum weight enumerators. We establish an indirect linear relationship between these generalized quantum weight enumerators by introducing an auxiliary exact weight enumerator that completely quantifies the quantum code’s projector, and is independent of the underlying noise process. By additionally working within the framework of approximate quantum error correction, we establish a general framework for constructing a linear program that is infeasible whenever approximate quantum error correcting codes with corresponding parameters do not exist. Our linear programming framework allows us to establish the non-existence of certain quantum codes that approximately correct amplitude damping errors, and obtain non-trivial upper bounds on the maximum dimension of a broad family of permutation-invariant quantum codes. [ABSTRACT FROM AUTHOR]

We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal. [ABSTRACT FROM AUTHOR]

We consider the problem of covert communication over a state-dependent channel when the Channel State Information (CSI) is available either non-causally, causally, or strictly causally, either at the transmitter alone, or at both transmitter and receiver. Covert communication with respect to an adversary, called “warden,” is one in which, despite communication over the channel, the warden’s observation remains indistinguishable from an output induced by innocent channel-input symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a large shared key at the transmitter and legitimate receiver. Instead, we only require a secret key with negligible rate to bootstrap the communication and our scheme extracts shared randomness from the CSI in a manner that keeps it secret from the warden, despite the influence of the CSI on the warden’s output. When CSI is available at the transmitter and receiver, we derive the covert capacity region. When CSI is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We also provide examples for which the covert capacity is positive with knowledge of CSI but is zero without it. [ABSTRACT FROM AUTHOR]

Additive codes have become an increasingly important topic in algebraic coding theory due to their applications in quantum error-correction and quantum computing. Linear Complementary Dual (LCD) codes play an important role for improving the security of information against certain attacks. Motivated by these facts, we define additive complementary dual codes (ACD for short) over a finite abelian group in terms of an arbitrary duality on the ambient space and examine their properties. We show that the best minimum weight of ACD codes is always greater than or equal to the best minimum weight of LCD codes of the same size and that this inequality is often strict. We give some matrix constructions for quaternary ACD codes from a given quaternary ACD code and also from a given binary self-orthogonal code. Moreover, we construct an algorithm to determine if a given quaternary additive code is an ACD code with respect to all possible symmetric dualities. We also determine the largest minimum distance of quaternary ACD codes for lengths $n \leq 10$. The obtained codes are either optimal or near optimal according to Bierbrauer et al +. (2009). [ABSTRACT FROM AUTHOR]

We show that one of the Shor-Laflamme weight enumerators of a codeword stabilized quantum code may be interpreted as the distance enumerator of an associated classical code. [ABSTRACT FROM AUTHOR]

We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that gets as input a set of points in space, and find a corresponding set of codewords from the Reed-Muller code that are jointly not farther away from the input than the upper bound on the generalized covering radius of the code. We prove that the algorithm runs in time that is polynomial in the code parameters. [ABSTRACT FROM AUTHOR]

Motivated by applications to DNA storage, we study reconstruction and list-reconstruction schemes for integer vectors that suffer from limited-magnitude errors. We characterize the asymptotic size of the intersection of error balls in relation to the code’s minimum distance. We also devise efficient reconstruction algorithms for various limited-magnitude error parameter ranges. We then extend these algorithms to the list-reconstruction scheme, and show the trade-off between the asymptotic list size and the number of required channel outputs. These results apply to all codes, without any assumptions on the code structure. Finally, we also study linear reconstruction codes with small intersection, as well as show a connection to list-reconstruction codes for the tandem-duplication channel. [ABSTRACT FROM AUTHOR]

We consider the problem of secure distributed matrix computation (SDMC), where a user queries a function of data matrices generated at distributed source nodes. We assume the availability of $N$ honest but curious computation servers, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the upload cost, while guaranteeing that no $T$ colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, and to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any $T$ colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure. [ABSTRACT FROM AUTHOR]

We prove that the covering radius of the Melas code $M(m,q)$ of length $n=q^{m}-1$ over $\mathbb {F}_{q}$ is 2 if $q > 3$. We also prove that the covering radius of $M(m,3)$ is 3 is $m \ge 3$ , the covering radius of $M(2,3)$ is 4, and the covering radii of $M(1,2)$ and $M(1,3)$ are 1. [ABSTRACT FROM AUTHOR]

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running “coded” copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings. [ABSTRACT FROM AUTHOR]

We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well. [ABSTRACT FROM AUTHOR]

We show that the problem of code construction for multiple access channel (MAC) resolvability can be reduced to the simpler problem of code construction for source resolvability. Specifically, we propose a MAC resolvability code construction that relies on a combination of multiple source resolvability codes, used in a black-box manner, and leverages randomness recycling implemented via distributed hashing and block-Markov coding. Since explicit source resolvability codes are known, our results also yield the first explicit coding schemes that achieve the entire MAC resolvability region for any discrete memoryless multiple-access channel with binary input alphabets. [ABSTRACT FROM AUTHOR]

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate—that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error—is $O(1/\sqrt {n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede’s wringing technique. The $O(1/\sqrt {n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt {n})$ term, although for most channels they do not match existing achievable bounds. [ABSTRACT FROM AUTHOR]

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error. [ABSTRACT FROM AUTHOR]

We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way. [ABSTRACT FROM AUTHOR]

List-decodability of Reed–Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form $r=1-\varepsilon $ for $\varepsilon $ tending to zero. Our main result states that there exist Reed–Solomon codes with rate $\Omega (\varepsilon)$ which are $(1-\varepsilon, O(1/\varepsilon))$ -list-decodable, meaning that any Hamming ball of radius $1-\varepsilon $ contains at most $O(1/\varepsilon)$ codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance. [ABSTRACT FROM AUTHOR]

This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter $p$ (${\mathrm {BDC}}_{p}$) every bit is deleted independently with probability $p$. A lower bound of $(1-p)/9$ is known on the capacity of the ${\mathrm {BDC}}_{p}$ , yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate $(1-p)/16$ , for every $p$. This improves upon the work of Guruswami and Li (2018) that gave a construction of rate $(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter $\lambda $ (PRC $_{\lambda }$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean $\lambda $. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC $_{\lambda }$. [ABSTRACT FROM AUTHOR]

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$ , binary linear codes of block length $O(1/\delta ^{2+\alpha })$ and rate $I(W)-\delta $ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length $O(1/\delta ^{2})$. This quadratic dependence on the gap $\delta $ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity. [ABSTRACT FROM AUTHOR]