Search

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]

The rate regions of multilevel diversity coding systems (MDCSs), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated in a systematic way. We enumerate all non-isomorphic MDCS instances with at most three sources and four encoders. Then, the exact rate region of every one of these more than 7000 instances is proven via computations showing that the Shannon outer bound matches with a custom constructed linear code-based inner bound. Results gained from these computations are summarized in key statistics involving aspects, such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, and so on. Also, it is shown how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases of arbitrary size that they inspired is introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes is presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which scalar binary (superposition) codes are insufficient down to 12 (26) forbidden the smallest embedded MDCS instances. [ABSTRACT FROM PUBLISHER]

In this paper, we present a fast Fourier transform algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires \mathcal O(h\lg (h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/decoding algorithms for (n=2^{m},k) Reed–Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires \mathcal {O}(n\lg (n))$ , in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed. [ABSTRACT FROM AUTHOR]

We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε > 0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ = 2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2 × 2 kernel) on the BEC is μ = 3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ × ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ (ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ (ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(n log n). [ABSTRACT FROM AUTHOR]

Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$ . For odd $L\ge 3$ , an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the best known bound (due to Blinovsky’1986) for rates below a certain threshold. The method is a superposition of the linear-programming idea of Ashikhmin, Barg, and Litsyn (that was previously used to improve the estimates of Blinovsky for $L=2$ ) and a Ramsey-theoretic technique of Blinovsky. As an application, it is shown that for all odd $L$ , the slope of the rate-radius tradeoff is zero at zero rate. [ABSTRACT FROM AUTHOR]

We leverage proof techniques from discrete Fourier analysis and an existing result in coding theory to derive new bounds for the problem of non-interactive simulation of binary random variables. Previous bounds in the literature were derived by applying data processing inequalities concerning maximal correlation or hypercontractivity. We show that our bounds are sharp in some regimes. Indeed, for a specific instance of the problem parameters, our main result resolves an open problem posed by E. Mossel in 2017. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established. [ABSTRACT FROM AUTHOR]

We say that a $q$ -ary length n$ code is non-overlapping if the set of non-trivial prefixes of codewords and the set of non-trivial suffices of codewords are disjoint. These codes were first studied by Levenshtein in 1964, motivated by applications in synchronization. More recently these codes were independently invented (under the name cross-bifix-free codes) by Bajić and Stojanović. We provide a simple construction for a class of non-overlapping codes which has optimal cardinality whenever n$ divides q$ . Moreover, for all parameters n$ and q$ , we show that a code from this class is close to optimal, in the sense that it has cardinality within a constant factor of an upper bound due to Levenshtein from 1970. Previous constructions have cardinality within a constant factor of the upper bound only when q$ is fixed. Chee, Kiah, Purkayastha, and Wang showed that a codewords; this bound is weaker than the Levenshtein bound. Their proof appealed to the application in synchronization: we provide a direct combinatorial argument to establish the bound of Chee et al. We also consider codes of short length, finding the leading term of the maximal cardinality of a non-overlapping code when $n$ is fixed and $q\rightarrow \infty $ . The largest cardinality of non-overlapping codes of lengths 3 or less is determined exactly. [ABSTRACT FROM AUTHOR]

We analyze the optimal tradeoff between the error exponent and the excess-rate exponent for variable-rate Slepian–Wolf codes. In particular, we first derive upper (converse) bounds on the optimal error and excess-rate exponents, and then lower (achievable) bounds, via a simple class of variable-rate codes which assign the same rate to all source blocks of the same type class. Then, using the exponent bounds, we derive bounds on the optimal rate functions, namely, the minimal rate assigned to each type class, needed in order to achieve a given target error exponent. The resulting excess-rate exponent is then evaluated. Iterative algorithms are provided for the computation of both bounds on the optimal rate functions and their excess-rate exponents. The resulting Slepian–Wolf codes bridge between the two extremes of fixed-rate coding, which has minimal error exponent and maximal excess-rate exponent, and average-rate coding, which has maximal error exponent and minimal excess-rate exponent. [ABSTRACT FROM AUTHOR]

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters. [ABSTRACT FROM PUBLISHER]

Let ${T}_{ \epsilon }$ , $0 \le \epsilon \le 1/2$ , be the noise operator acting on functions on the boolean cube $\{0,1\}^{n}$. Let $f$ be a nonnegative function on $\{0,1\}^{n}$ and let ${q} \ge 1$. We upper bound the $\ell _{{q}}$ norm of ${T}_{ \epsilon } {f}$ by the average $\ell _{{q}}$ norm of conditional expectations of f, given sets of roughly $(1-2 \epsilon)^{{r}({q})} \cdot {n}$ variables, where r is an explicitly defined function of q. We describe some applications for error-correcting codes and for matroids. In particular, we derive an upper bound on the weight distribution of BEC-capacity achieving binary linear codes and their duals. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for all (constant) rates. [ABSTRACT FROM AUTHOR]

A ${\mathbb {Z}}_{2}{\mathbb {Z}}_{4}$ -additive code ${\mathcal{ C}}\subseteq {\mathbb {Z}}_{2}^\alpha \times {\mathbb {Z}}_{4}^\beta $ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb {Z}}_{2}$ and the set of ${\mathbb {Z}}_{4}$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. We study the binary images of $\mathbb {Z}_{2} \mathbb {Z}_{4} $ -additive cyclic codes. We determine all ${\mathbb {Z}_{2}\mathbb {Z}_{4}}$ -additive cyclic codes with odd $\beta $ whose Gray images are linear binary codes. In this case, it is shown that such binary codes are permutation equivalent (by the Nechaev permutation) to $\mathbb {Z}_{2}$ -double cyclic codes. Finally, the generator polynomials of these binary codes are given. [ABSTRACT FROM AUTHOR]

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs. [ABSTRACT FROM AUTHOR]

We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality. [ABSTRACT FROM AUTHOR]

In highly dynamic wireless networks, communications face several challenges. In the first place, noise levels between nodes might be difficult to predict a priori. Besides, a Byzantine attacker hidden in the network, with knowledge of the network topology and observation of all transmissions, can choose arbitrary locations to inject corrupted packets. Considering that transmissions are usually in bits and hardware in wireless networks usually use modulation schemes with the size of modulation alphabet being powers of two, e.g. BPSK, QPSK, 16-QAM, 64-QAM, and so on, to address the above problem, we study coding for networks experiencing worst case bit errors, and with network codes over binary extension fields. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. A new transform metric for errors under the considered model is proposed. Using this metric, we replicate many of the classical results from coding theory. Specifically, new Hamming-type, Plotkin-type, and Elias-Bassalygo-type upper bounds on the network capacity are derived. A commensurate lower bound is shown based on Gilbert–Varshamov (GV)-type codes for error-correction. The GV codes used to attain the lower bound can be non-coherent, that is, they require neither prior knowledge of the network topology nor network coding kernels. We also propose a computationally efficient concatenation scheme. The rate achieved by our concatenated codes is characterized by a Zyablov-type lower bound. We provide a generalized minimum-distance decoding algorithm which decodes up to half the minimum distance of the concatenated codes. The end-to-end nature of our design enables our codes to be overlaid on the classical distributed random linear network codes. The other advantage of the end-to-end strategy over the link-by-link error-correction is that it reduces the computational cost at the internal nodes for performing error-correction. [ABSTRACT FROM PUBLISHER]

We study the problem of characterizing when two memoryless binary asymmetric channels, described by their transition probabilities $(p,q)$ and $(p^\prime,q^\prime)$ , are equivalent from the point of view of maximum likelihood decoding when restricted to $n$ -block binary codes. This equivalence of channels induces a partition (depending on $n$ ) on the space of parameters $(p,q)$ into regions associated with the equivalence classes. Explicit expressions for describing these regions, their number and areas are derived. Some perspectives of applications of our results to decoding problems are also presented. [ABSTRACT FROM PUBLISHER]

We propose a new coded caching scheme where linear combinations of the file segments are cached at the users, for the cases where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interference. The proposed scheme combines rank-metric codes and maximum distance-separable codes to facilitate the decoding and elimination of the interference and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that it can achieve improvement over known memory-rate tradeoff achievable results in the literature in some regime; for certain special cases, the new memory-rate tradeoff points can be shown to be optimal. [ABSTRACT FROM PUBLISHER]

The construction of deletion codes for the editing metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of lattices’ translates. These lattices, in turn, are obtained from Construction A applied to binary codes and \mathbb Z4 –codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices. For any fixed number of deletions, provided the number of runs is large enough our method supplies a correction technique. For fixed number of runs and binary sequence length large our lattice construction is shown to be tight up to constants. [ABSTRACT FROM PUBLISHER]

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate. [ABSTRACT FROM PUBLISHER]

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs. [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]

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]

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]

The bilateral minimum distance of a binary linear code is the maximum d such that all nonzero codewords have weights between d and n-d . Let be a binary linear code whose dual has bilateral minimum distance at least d , where d is odd. Roughly speaking, we show that the average L_\infty -distance—between the weight distribution of a random cosets of Q and the binomial distribution decays quickly as the bilateral minimum distance d of the dual of Q increases. For d = \Theta (1) . On the other d=\Theta (n) extreme, it decays like and e^{-\Theta (d)} . It follows that, almost all cosets of Q have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of Q has bilateral minimum distance at least d=2t+1 , where t\geq 1 -distance is at most \min \ (e\ln (n/2t))^t(2t/n)^(t/2), \sqrt 2 e^-(t/10)\ . For the average L1 -distance, we conclude the bound \min \ (2t+1)(e\ln (n/2t))^t (2t/n)^(t/2)-1, \sqrt 2(n+1)e^-(t/10)\ , which gives nontrivial results for $t\geq 3$ . We give applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques. [ABSTRACT FROM PUBLISHER]

A coding scheme of (k+1) -ary error-correcting signature codes for a noisy multiple-access adder channel is proposed. Given a signature matrix A and a difference matrix D=D^+-D^- a priori, a larger signature matrix is obtained by replacing each element in the Hadamard matrix with A , or D^+ , or D^- depending on the values of the elements and their locations in the Hadamard matrix. The set of rows in the proposed matrix gives an error-correcting signature code. Introducing a difference matrix makes it possible to construct an error-correcting signature code whose sum rate is increased with an increase in the order of the Hadamard matrix. Either binary or non-binary signature codes are constructed when the pairs of matrices $A$ and $D$ are given. [ABSTRACT FROM PUBLISHER]

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]

We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captures the benefit of side information for performing inference on a random variable under this loss function. When such a measure satisfies a natural data processing property, and the random variable of interest has alphabet size greater than two, we show that it is uniquely characterized by the mutual information, and the corresponding loss function coincides with logarithmic loss. In doing so, our work provides a new characterization of mutual information, and justifies its use as a measure of relevance. When the alphabet is binary, we characterize the only admissible forms the measure of relevance can assume while obeying the specified data processing property. Our results naturally extend to measuring the causal influence between stochastic processes, where we unify different causality measures in the literature as instantiations of directed information. [ABSTRACT FROM PUBLISHER]

We consider the Gaussian wiretap channel with amplitude and variance constraints on the channel input. We first show that the entire rate-equivocation region of the Gaussian wiretap channel with an amplitude constraint is obtained by discrete input distributions with finite support. We prove this result by considering the existing single-letter description of the rate-equivocation region, and showing that discrete distributions with finite support exhaust this region. Our result highlights an important difference between the peak power (amplitude) constrained and the average power (variance) constrained cases. Although, in the average power constrained case, both the secrecy capacity and the capacity can be achieved simultaneously, our results show that in the peak power constrained case, in general, there is a tradeoff between the secrecy capacity and the capacity, in the sense that, both may not be achieved simultaneously. We also show that under sufficiently small amplitude constraints the possible tradeoff between the secrecy capacity and the capacity does not exist and they are both achieved by the symmetric binary distribution. Finally, we prove the optimality of discrete input distributions in the presence of an additional variance constraint. [ABSTRACT FROM PUBLISHER]

We study statistical restricted isometry, a property closely related to sparse signal recovery, of deterministic sensing matrices of size m \times N . A matrix is said to have a statistical restricted isometry property (StRIP) of order k if most submatrices with k columns define a near-isometric map of into {\mathbb R}^{m} . As our main result, we establish sufficient conditions for the StRIP property of a matrix in terms of the mutual coherence and mean square coherence. We show that for many existing deterministic families of sampling matrices, m=O(k)$ rows suffice for $k$ -StRIP, which is an improvement over the known estimates of either $m = \Theta (k \log N)$ or $m = \Theta (k\log k)$ . We also give examples of matrix families that are shown to have the StRIP property using our sufficient conditions. [ABSTRACT FROM PUBLISHER]

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert–Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval [0,0.0668] . One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval \tau \in (0,{1}/{8}] and meets the lower bound of {1}/{2} for \tau \geq 1/8 . Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t -grain-correcting codes of length $n$ , for certain values of n$ and t$ . Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of on the minimum redundancy of $\infty $ -grain-detecting codes of length $n$ is presented. [ABSTRACT FROM PUBLISHER]

We propose a lattice construction from totally real and complex multiplication fields, which naturally generalizes Construction A of lattices from p -ary codes obtained from the cyclotomic field \mathbb {Q}(\zeta _{p}) , p a prime, which in turn contains the so-called Construction A of lattices from binary codes as a particular case. We focus on the maximal totally real subfield \mathbb Q(\zeta p^{r}\,+\,\zeta p^{-r}) of the cyclotomic field \mathbb Q(\zeta p^{r}) , $r\geq 1$ . Our construction has applications to coset encoding of algebraic lattice codes for block fading channels, and in particular for block fading wiretap channels. [ABSTRACT FROM AUTHOR]

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast that arises between the binary-alphabet and larger alphabet settings. This is surprising in some instances, since characterizations for the larger alphabet settings do not generalize their binary-alphabet counterparts. In particular, we show that $f $ -divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that Kullback–Leibler (KL) divergence is the unique Bregman divergence, which is also an $f $ -divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence, which is invariant to statistically sufficient transformations of the data, even when nondecomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three. [ABSTRACT FROM AUTHOR]

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a \((1/4 -\epsilon )\) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a multiplicative factor that depends only on \(\epsilon \) , using an alphabet whose size depends only on \(\epsilon \) . This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication, and tolerating a \(1/8 -\epsilon \) fraction of errors. [ABSTRACT FROM PUBLISHER]

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]

In this work, we present a family of vector quantization schemes vqSGD (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact: $\Theta \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive $O(\log d)$ term) to describe an unbiased estimator $\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any $\boldsymbol {g}$ in the $d$ -dimensional unit sphere, under the constraint that $\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely, $R > 1$. In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a $d$ -dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees. [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]

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]

In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code. Using these algorithms, we demonstrate—both with a heuristic analysis and in practice—a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off. The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. [ABSTRACT FROM AUTHOR]

We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-\delta) \approx 0.78974$ , where $h(\cdot)$ is the binary entropy function and $\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log _{2} n) / r$ as $n \to \infty $. [ABSTRACT FROM AUTHOR]

A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$. It is said to be list-recoverable for input list size $\ell $ if for every sufficiently large subset of at least $L$ codewords, there is a coordinate where the codewords take more than $\ell $ values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below $q$ is the alphabet size, and $ \varepsilon > 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log _{q}(\ell) - \varepsilon $ requires list size $L \ge \ell ^{\Omega (1/ \varepsilon)}$ for list-recovery from input list size $\ell $. (2) A random linear code of rate $1 - h_{q}(p) - \varepsilon $ requires list size $L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $ for list-decoding from error fraction $p$. (3) A random binary linear code of rate $1 - h_{2}(p) - \varepsilon $ is list-decodable from average error fraction $p$ with list size with $L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018). [ABSTRACT FROM AUTHOR]

We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by $q$ -ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family. For any desired $\varepsilon > 0$ , we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma $ fraction of insertions and $\delta $ fraction of deletions as long as $\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any $\gamma, \delta $ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$ -piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of $\delta,\gamma $ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. [ABSTRACT FROM AUTHOR]

We study the codes of the title by the CRT method, that decomposes such codes into constituent codes, which are shorter codes over larger alphabets. Criteria on these constituent codes for self-duality and linear complementary duality of the decomposed codes are derived. The special class of the one-generator codes is given a polynomial representation and exactly enumerated. In particular, we present some illustrative examples of binary optimal linear codes with respect to the Griesmer bound derived from the $\mathbb {Z}_{2} \mathbb {Z}_{4}$ -additive quasi-cyclic codes. [ABSTRACT FROM AUTHOR]

The bee identification problem is a problem of properly recognizing a massive amount of data (a numerous amount of bees in a beehive, for example) which have been mixed and corrupted by noise. We derive various error exponents in the bee identification problem under two different decoding rules. Under naïve decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds. [ABSTRACT FROM AUTHOR]

We give an explicit construction of length- $n$ binary codes capable of correcting the deletion of two bits that have size $2^{n}/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $\Omega (2^{n}/n^{4})$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $\Omega (2^{n}/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear. [ABSTRACT FROM AUTHOR]

The Byzantine distributed quickest change detection (BDQCD) is studied, where a fusion center monitors the occurrence of an abrupt event through a bunch of distributed sensors that may be compromised. We first consider the binary hypothesis case where there is only one post-change hypothesis and prove a novel converse to the first-order asymptotic detection delay in the large mean time to a false alarm regime. This converse is tight in that it coincides with the currently best achievability shown by Fellouris et al.; hence, the optimal asymptotic performance of binary BDQCD is characterized. An important implication of this result is that, even with compromised sensors, a 1-bit link between each sensor and the fusion center suffices to achieve asymptotic optimality. To accommodate multiple post-change hypotheses, we then formulate the multi-hypothesis BDQCD problem and again investigate the optimal first-order performance under different bandwidth constraints. A converse is first obtained by extending our converse from binary to multi-hypothesis BDQCD. Two families of stopping rules, namely the simultaneous d-th alarm and the multi-shot d-th alarm, are then proposed. Under sufficient link bandwidth, the simultaneous d-th alarm, with d being set to the number of honest sensors, can achieve the asymptotic performance that coincides with the derived converse bound; hence, the asymptotically optimal performance of multi-hypothesis BDQCD is again characterized. Moreover, although being shown to be asymptotically optimal only for some special cases, the multi-shot d-th alarm is much more bandwidth-efficient and energy-efficient than the simultaneous d-th alarm. Built upon the above success in characterizing the asymptotic optimality of the BDQCD, a corresponding leader-follower Stackelberg game is formulated and its solution is found. [ABSTRACT FROM AUTHOR]

Error-correcting codes that admit local decoding and correcting algorithms have been the focus of much recent research due to their numerous applications. An important goal is to obtain the best possible tradeoffs between the number of symbols of the codeword that the local decoding algorithm must examine (the locality), and the amount of redundancy in the encoding (the information rate). In Hamming’s classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality but superpolynomial blocklength, or small blocklength but high locality. However, in the computationally bounded adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions. We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no trusted setup. The only assumption we require is the selection of the public parameters (seed) for a collision-resistant hash function. Specifically, we provide constructions of relaxed locally correctable and relaxed locally decodable codes over the binary alphabet, with constant information rate, and poly-logarithmic locality. Our constructions, which compare favorably with their classical analogs, crucially employ collision-resistant hash functions and local expander graphs, extending ideas from recent cryptographic constructions of memory-hard functions. [ABSTRACT FROM AUTHOR]

Let p ≥ 2. We improve the bound ||ƒ||p/||ƒ||2 ≤ (p−1)s/2 for a polynomial ƒ of degree s on the boolean cube {0,1}n, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of p and s, which is smaller than (p−1)s/2 for any p > 2 and s > 0. We show the new bound to be tight, within a smaller order factor, for the Krawchouk polynomial of degree s. This implies several nearly-extremal properties of Krawchouk polynomials and Hamming spheres (equivalently, Hamming balls). In particular, Krawchouk polynomials have (almost) the heaviest tails among all polynomials of the same degree and ℓ2 norm. The Hamming spheres have the following approximate edge-isoperimetric property: For all 1 ≤ s ≤ n/2, and for all even distances 0 ≤ i ≤ 2s(n-s)/n, the Hamming sphere of radius s contains, up to a multiplicative factor of O(i), as many pairs of points at distance i as possible, among sets of the same size (there is a similar, but slightly weaker and somewhat more complicated claim for all distances). This also implies that Hamming spheres are (almost) stablest with respect to noise among sets of the same size. In coding theory terms this means that a Hamming sphere (equivalently a Hamming ball) has the maximal probability of undetected error, among all binary codes of the same rate. We also describe a family of hypercontractive inequalities for functions on {0,1}n, which improve on the ‘usual’ “q → 2” inequality by taking into account the concentration of a function (expressed as the ratio between its ℓr norms), and which are nearly tight for characteristic functions of Hamming spheres. 1 This has to be interpreted with some care. [ABSTRACT FROM AUTHOR]

We obtain a characterization on self-orthogonality for a given binary linear code in terms of the number of column vectors in its generator matrix, which extends the result of Bouyukliev et al. (2006). As an application, we give an algorithmic method to embed a given binary k-dimensional linear code C (k = 3,4) into a self-orthogonal code of the shortest length which has the same dimension k and minimum distance d' ≥ d(C). For k > 4, we suggest a recursive method to embed a k -dimensional linear code to a self-orthogonal code. We also give new explicit formulas for the minimum distances of optimal self-orthogonal codes for any length n with dimension 4 and any length n ≢ 6, 13,14,21,22,28,29 (mod 31) with dimension 5. [ABSTRACT FROM AUTHOR]

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉ + O(log log n) redundancy bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth’s balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit. [ABSTRACT FROM AUTHOR]