Search

We consider the problem of communicating over a channel that randomly “tears” the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\mathrm{ Geometric}}(p_{n})$ , we characterize the capacity as $C = e^{-\alpha }$ , where $\alpha = \lim _{n\to \infty } p_{n} \log n$. Our results show that the case of ${\mathrm{ Geometric}}(p_{n})$ -length fragments and the case of deterministic length- $(1/p_{n})$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity. [ABSTRACT FROM AUTHOR]

An $(r, \delta)$ -locally repairable code ($(r, \delta)$ -LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$ -LRCs produced by Gopalan et al.. An $(r, \delta)$ -LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. generalized the construction of cyclic $r$ -LRCs proposed by Tamo et al. , and constructed several classes of optimal $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of , , this paper first characterizes $(r, \delta)$ -locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively from the product of two sets of zeros. Our constructions include all optimal cyclic $(r,\delta)$ -LRCs proposed in , , and our method seems more convenient to obtain optimal cyclic $(r, \delta)$ -LRCs with flexible parameters. Moreover, many optimal cyclic $(r,\delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively with $(r+\delta -1)\nmid n$ can be obtained from our method. [ABSTRACT FROM AUTHOR]

Linear codes achieving or nearly achieving the Singleton bound are interesting in both theory and practice. The objective of this paper is to construct several infinite families of MDS, near MDS and almost MDS codes from some special cyclic subgroups of ${\mathbb {F}}_{q^{2}}^{*}$. To this end, the augmentation and extension techniques are used. The codes in this paper have flexible parameters and their lengths could be large. The minimum linear locality of the codes constructed in this paper is also studied. Some infinite families of optimal linearly locally recoverable codes are obtained. Besides, some codes in this paper are proved to be proper for error detection. [ABSTRACT FROM AUTHOR]

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

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

Recently, subfield codes of geometric codes over large finite fields ${\mathrm {GF}}(q)$ with dimension 3 and 4 were studied and distance-optimal subfield codes over ${\mathrm {GF}}(p)$ were obtained, where $q=p^{m}$. The key idea for obtaining very good subfield codes over small fields is to choose very good linear codes over an extension field with small dimension. This paper first presents a general construction of $[q+1, 2, q]$ MDS codes over ${\mathrm {GF}}(q)$ , and then studies the subfield codes over ${\mathrm {GF}}(p)$ of some of the $[q+1, 2,q]$ MDS codes over ${\mathrm {GF}}(q)$. Two families of dimension-optimal codes over ${\mathrm {GF}}(p)$ are obtained, and several families of nearly optimal codes over ${\mathrm {GF}}(p)$ are produced. Several open problems are also proposed in this paper. [ABSTRACT FROM AUTHOR]

Linear codes with few weights have applications in consumer electronics, communications, data storage systems, secret sharing, authentication codes, and association schemes. As a special class of linear codes, minimal linear codes have important applications in secret sharing and secure computation of data between two parties. The construction of minimal linear codes with new and desirable parameters is an interesting research topic in coding theory and cryptography. Recently, Mesnager et.al. stated that “constructing linear codes with good parameters from non-weakly regular bent functions is an interesting problem.” The goal of this paper is to construct linear codes with two or three weights from non-weakly regular bent functions over finite fields and analyze the minimality of the constructed linear codes. In doing so, we draw inspiration from a paper by Mesnager in which she constructed linear codes with small weights from weakly regular bent functions based on a generic construction method. First, we recall the definitions of the subsets $B_{+}(f)$ and $B_{-}(f)$ associated with a non-weakly regular bent function $f$. Next, we construct two- or three-weight linear $p$ -ary codes on these sets using duals of the non-weakly regular bent functions that are also bent. We note that the constructed linear codes are minimal in almost all cases. Moreover, when $f$ is a non-weakly regular bent function in a certain subclass of Generalized Maiorana-McFarland bent functions, we determine the weight distributions of the corresponding linear codes. As far as we know, the construction of linear codes from non-weakly regular bent functions over finite fields is first studied in the literature by the second author in his dissertation. [ABSTRACT FROM AUTHOR]

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size ${\mathsf M}$ and the network load ${\mathsf R}$ for the networks where a server with ${\mathsf N}$ files is connected to ${\mathsf H}$ relays (without caches), which in turn are connected to ${\mathsf K}$ users equipped with caches of ${\mathsf M}$ files. When each user is connected to a different subset of ${\mathsf r}$ relays, i.e., ${\mathsf K}= \binom {\mathsf H}{\mathsf r}$ , the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some $({\mathsf N}, {\mathsf M}, {\mathsf H}, {\mathsf r})$ parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations. [ABSTRACT FROM AUTHOR]

Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair $(f,g)$ of binary sequences (i.e., sequences with terms in {−1, 1}). If $f$ is a nonzero sequence, then its autocorrelation demerit factor, $\text {ADF}(f)$ , is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing $f$ to have unit Euclidean norm. If $(f,g)$ is a pair of nonzero sequences, then their crosscorrelation demerit factor, $\text {CDF}(f,g)$ , is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both $f$ and $g$ to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of $\text {CDF}(f,g)$ and the geometric mean of $\text {ADF}(f)$ and $\text {ADF}{(g)}$ must be at least 1. For randomly selected pairs of long binary sequences, this quantity is typically around 2. In this paper, we show that Pursley and Sarwate’s bound is met for binary sequences precisely when $(f,g)$ is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families. [ABSTRACT FROM AUTHOR]

The topological interference management (TIM) problem refers to the study of the $K$ -user partially connected interference networks with no channel state information at the transmitters (CSIT), except for the knowledge of network topology. In this paper, we study the TIM problem with confidential messages (TIM-CM), where message confidentiality must be satisfied in addition to reliability constraints. In particular, each transmitted message must be decodable at its intended receiver and remain confidential at the remaining $(K-1)$ receivers. Our main contribution is to present a comprehensive set of results for the TIM-CM problem by studying the symmetric secure degrees of freedom (SDoF). To this end, we first characterize necessary and sufficient conditions for feasibility of positive symmetric SDoF for any arbitrary topology. We next present two achievable schemes for the TIM-CM problem: For the first scheme, we use the concept of secure partition and, for the second one, we use the concept of secure independent sets. We also present outer bounds on symmetric SDoF for any arbitrary network topology. Using these bounds, we characterize the optimal symmetric SDoF of all $K=2$ -user and $K=3$ -user network topologies. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by C(ƒ) = {Tr(aƒ(x) + bx)x∈Fqm*: a, b ∈ Fqm}, where q is a prime power, Fqm* = Fqm \ {0}, Tr is the trace function from Fqm to Fq, and ƒ(x) is a function from Fqm to Fqm with ƒ(0) = 0. Almost bent functions, quadratic functions and some monomials on F2m were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper. [ABSTRACT FROM AUTHOR]

The puncturing and shortening techniques are two important approaches to constructing new linear codes from old ones. In the past 70 years, a lot of progress on the puncturing technique has been made, and many works on punctured linear codes have been done. Many families of linear codes with interesting parameters have been obtained with the puncturing technique. However, little research on the shortening technique has been done and there are only a handful references on shortened linear codes. The first objective of this paper is to prove some general theory for shortened linear codes. The second objective is to study some shortened codes of the Hamming codes, Simplex codes, some Reed-Muller codes, and ovoid codes. Eleven families of optimal shortened codes over finite fields are presented in this paper. As a byproduct, five infinite families of 2-designs are also constructed from some of the shortened codes presented in this paper. [ABSTRACT FROM AUTHOR]

Let m be an even positive integer. A Boolean bent function ƒ on F2m-1 × F2 is called a cyclic bent function if for any a ≠ b ∈ F2m-1 and ε ∈ F2, ƒ(ax1, x2)+ ƒ(bx1, x2 + ε) is always bent, where x1 ∈ F2m-1, x2 ∈ F2. Cyclic bent functions look extremely rare. This paper focuses on cyclic bent functions on F2m-1 × F2 and their applications. The first objective of this paper is to establish a link between quadratic cyclic bent functions and a special type of prequasifields, and construct a class of quadratic cyclic bent functions from the Kantor-Williams prequasifields. The second objective is to use cyclic bent functions to construct families of optimal sequences. The results of this paper show that cyclic bent functions have nice applications in several fields such as coding theory, symmetric cryptography, and CDMA communication. [ABSTRACT FROM AUTHOR]

In this paper, we provide the left and right Parseval relations over the quaternions. Moreover, we construct a new infinite family of sequences almost over $Q_{8} $ with period $p$ by a generalization of Legendre mapping, where $p\equiv 1 \pmod {8}$ is prime and the sequences have ideal autocorrelation. The sequences are symmetric when $p\equiv 1 \pmod {16}$ , and antisymmetric when $p\equiv 9 \pmod {16} $. [ABSTRACT FROM AUTHOR]

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every $T_{s}$ seconds and an erasure channel that can be used every $T_{c}$ seconds, we ask what is the coding strategy that minimizes the time-average “age of information” that an observer of the channel output incurs. We first analyze the case where the source alphabet and the channel-input alphabet have the same size. We show that a trivial coding strategy is optimal and a closed form expression for the age can be derived. We then analyze the case where the alphabets have different sizes. We use a random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age of linear block codes as the source alphabet becomes large. [ABSTRACT FROM AUTHOR]

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

In high-dimensional sparse regression, would increasing the signal-to-noise ratio while fixing the sparsity level always lead to better model selection? For high-dimensional sparse regression problems, surprisingly, in this paper we answer this question in the negative in the regime of linear sparsity for the Lasso method, relying on a new concept we term effect size heterogeneity. Roughly speaking, a regression coefficient vector has high effect size heterogeneity if its nonzero entries have significantly different magnitudes. From the viewpoint of this new measure, we prove that the false and true positive rates achieve the optimal trade-off uniformly along the Lasso path when this measure is maximal in a certain sense, and the worst trade-off is achieved when it is minimal in the sense that all nonzero effect sizes are roughly equal. Moreover, we demonstrate that the first false selection occurs much earlier when effect size heterogeneity is minimal than when it is maximal. The underlying cause of these two phenomena is, metaphorically speaking, the “competition” among variables with effect sizes of the same magnitude in entering the model. Taken together, our findings suggest that effect size heterogeneity shall serve as an important complementary measure to the sparsity of regression coefficients in the analysis of high-dimensional regression problems. Our proofs use techniques from approximate message passing theory as well as a novel technique for estimating the rank of the first false variable. [ABSTRACT FROM AUTHOR]

Tsallis and Rényi entropies, which are monotone transformations of each other, are deformations of the celebrated Shannon entropy. Maximization of these deformed entropies, under suitable constraints, leads to the $q$ -exponential family which has applications in non-extensive statistical physics, information theory and statistics. In previous information-geometric studies, the $q$ -exponential family was analyzed using classical convex duality and Bregman divergence. In this paper, we show that a generalized $\lambda $ -duality, where $\lambda = 1 - q$ is to be interpreted as the constant information-geometric curvature, leads to a generalized exponential family which is essentially equivalent to the $q$ -exponential family and has deep connections with Rényi entropy and optimal transport. Using this generalized convex duality and its associated logarithmic divergence, we show that our $\lambda $ -exponential family satisfies properties that parallel and generalize those of the exponential family. Under our framework, the Rényi entropy and divergence arise naturally, and we give a new proof of the Tsallis/Rényi entropy maximizing property of the $q$ -exponential family. We also introduce a $\lambda $ -mixture family which may be regarded as the dual of the $\lambda $ -exponential family, and connect it with other mixture-type families. Finally, we discuss a duality between the $\lambda $ -exponential family and the $\lambda $ -logarithmic divergence, and study its statistical consequences. [ABSTRACT FROM AUTHOR]

In this paper, we present a variable-length binary code for permutations of degree n, where n is a power of 2. The Lehmer code and its variants provide a bijection between permutations and the indexes in lexicographic ordering. They provide compression of permutations approaching Shannon bound at the expense of structural information. The variable-length code proposed in this paper has asymptotically optimal compression capability while preserving structural information of permutations. In other words, the code encodes the way a permutation is organized, and is optimal in the sense that the ratio of average codeword length and the entropy of permutations approaches 1 as n tends to infinity. The encoding and decoding are efficient. Like the Lehmer code and other enumerative codes, it is not necessary to construct look-up tables. The code is complete and satisfies the prefix condition. Furthermore, the codeword length indicates how “well shuffled” a permutation is. Permutations with longer codewords seem more “random.” An enumeration method of the variable-length code is also given by using T. Cover’s enumerative coding scheme and Schalkwijk code. This gives a different indexing from the Lehmer code. This work can be extended to the case of arbitrary $n$ in a straightforward way. [ABSTRACT FROM AUTHOR]

In this paper, we study the duals of generalized bent functions $f: V_{n}\rightarrow \mathbb {Z}_{p^{k}}$ , where $V_{n}$ is an $n$ -dimensional vector space over $\mathbb {F}_{p}$ and $p$ is an odd prime, $k$ is a positive integer. It is known that weakly regular generalized bent functions always appear in pairs since the dual of a weakly regular generalized bent function is also a weakly regular generalized bent function. The duals of non-weakly regular generalized bent functions can be generalized bent or not generalized bent. By generalizing the construction of Çeşmelioğlu et al., 2016, we provide an explicit construction of generalized bent functions whose duals can be generalized bent or not generalized bent. We show that the well-known direct sum construction and the generalized indirect sum construction given in Wang and Fu, 2021. can provide secondary constructions of generalized bent functions whose duals can be generalized bent or not generalized bent. By using the knowledge on ideal decomposition in cyclotomic fields, we prove that $f^{**}(x)=f(-x)$ if $f$ is a generalized bent function and its dual $f^{*}$ is also a generalized bent function. For any non-weakly regular generalized bent function $f$ which satisfies that $f(x)=f(-x)$ and its dual $f^{*}$ is generalized bent, we give a property and as a consequence, we prove that there is no self-dual generalized bent function $f: V_{n}\rightarrow \mathbb {Z}_{p^{k}}$ if $p\equiv 3 ~(mod ~4)$ and $n$ is odd. When $p \equiv 1 ~(mod ~4)$ or $p\equiv 3 ~(mod ~4)$ and $n$ is even, we give a secondary construction of self-dual generalized bent functions. In the end, by the decomposition of generalized bent functions, we characterize the relations between the generalized bentness of the dual of a generalized bent function $f$ and the bentness of the duals of bent functions associated with the generalized bent function $f$ , as well as the relations of self-duality between a generalized bent function $f$ and bent functions associated with the generalized bent function $f$. [ABSTRACT FROM AUTHOR]

This paper describes new, simple, recursive methods of construction for orientable sequences, i.e. periodic binary sequences in which any $n$ -tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine $n$ consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Dai et al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences. [ABSTRACT FROM AUTHOR]

Tang and Ding [IEEE IT 67 (2021) 244-254] studied the class of BCH codes $\mathcal {C}_{(q,q+1,4,1)}$ and their dual codes with $q=2^{m}$ and established that the codewords of the minimum (or the second minimum) weight in these codes support 4-designs or 3-designs. Motivated by this, we further investigate the codewords of the next adjacent weight in such codes and discover more infinite classes of $t$ -designs with $t=3,4$. In particular, we prove that codewords of weight 7 in $\mathcal {C}_{(q,q+1,4,1)}$ support 4-designs for odd $m \geqslant 5$ and they support 3-designs for even $m \geqslant 4$ , which provide infinite classes of simple $t$ -designs with new parameters. Another significant class of $t$ -designs we produce in this paper has complementary designs with parameters 4- $(2^{2s+1}+ 1,5,5)$ ; these designs have the smallest index among all the known simple 4- $(q+1,5,\lambda)$ designs derived from codes for prime powers $q$ ; and they are further proved to be isomorphic to the 4-designs admitting the projective general linear group PGL $(2,2^{2s+1})$ as the automorphism group constructed by Alltop in 1969. [ABSTRACT FROM AUTHOR]

The Langberg-Médard multiple unicast conjecture claims that for a strongly reachable $k$ -pair network, there exists a feasible multi-flow with rate $(1,1, {\dots },1)$. In this paper, we confirm the conjecture for $k=3$. [ABSTRACT FROM AUTHOR]

Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every $k$ -tuple of consecutive entries is uniquely recoverable from its $l$ -neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the $k$ -tuple conditioned on its $l$ -neighborhood be bounded above by some $\epsilon >0$. We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an $\epsilon $ -recoverable measure from a corresponding deterministic system. [ABSTRACT FROM AUTHOR]

In 1994, Jim Massey proposed the guessing entropy as a measure of the difficulty that an attacker has to guess a secret used in a cryptographic system, and established a well-known inequality between entropy and guessing entropy. Over 15 years before, in an unpublished work, he also established a well-known inequality for the entropy of an integer-valued random variable of given variance. In this paper, we establish a link between the two works by Massey in the more general framework of the relationship between discrete (absolute) entropy and continuous (differential) entropy. Two approaches are given in which the discrete entropy (or Rényi entropy) of an integer-valued variable can be upper bounded using the differential (Rényi) entropy of some suitably chosen continuous random variable. As an application, lower bounds on guessing entropy and guessing moments are derived in terms of entropy or Rényi entropy (without side information) and conditional entropy or Arimoto conditional entropy (when side information is available). [ABSTRACT FROM AUTHOR]

Let $ \mathbb K$ be an algebraically closed field. In this paper, we consider the class of smooth plane curves of degree $n+1>3$ over $ \mathbb K$ , containing three points, $P_{1},P_{2}$ , and $P_{3}$ , such that $nP_{1}+P_{2}$ , $nP_{2}+P_{3}$ , and $nP_{3}+P_{1}$ are divisors cut out by three distinct lines. For such curves, we determine the dimension of certain special divisors supported on $\{P_{1},P_{2},P_{3}\}$ , as well as an explicit description of all pure gaps at each nonempty subset of the distinguished points $P_{1},P_{2}$ , and $P_{3}$. When $ \mathbb K=\overline { \mathbb F}_{q}$ , this class of curves, which includes the Hermitian curve, is used to construct algebraic geometry codes having minimum distance better than the Goppa bound. [ABSTRACT FROM AUTHOR]

For a function $f$ from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{n}$ , the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an “intermediate” concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it conveys a detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges. [ABSTRACT FROM AUTHOR]

A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of the data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, their data fields have large distance. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single symbol of redundancy. The results are first presented for the Hamming metric and are then extended for the edit distance. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

As a special subclass of cyclic codes, BCH codes have wide applications in communication and storage systems. A BCH code of length $n$ over $\mathbb {F}_{q}$ is always relative to an $n$ -th primitive root of unity $\beta $ in an extension field of $\mathbb {F}_{q}$ , and is called a dually-BCH code if its dual is also a BCH code relative to the same $\beta $. The question as to whether a BCH code is a dually-BCH code is in general very hard to answer. In this paper, an answer to this question for primitive narrow-sense BCH codes and projective narrow-sense ternary BCH codes is given. Sufficient and necessary conditions in terms of the designed distances $\delta $ will be presented to ensure that these BCH codes are dually-BCH codes. In addition, the parameters of the primitive narrow-sense BCH codes and their dual codes are investigated. Some lower bounds on minimum distances of the dual codes of primitive and projective narrow-sense BCH codes are developed. Especially for binary primitive narrow-sense BCH codes, the new bounds on the minimum distances of the dual codes improve the classical Sidel’nikov bound, and are also better than the Carlitz and Uchiyama bound for large designed distances $\delta $. The question as to what subclasses of cyclic codes are BCH codes is also answered to some extent. As a byproduct, the parameters of some subclasses of cyclic codes are also investigated. [ABSTRACT FROM AUTHOR]

The tight lower bound on the redundancy of optimal prefix-free codes in terms of a given symbol probability (not necessarily the largest or the smallest one) has been derived in the literature. The first goal of this paper is to derive the tight lower bounds in terms of $j$ ($j>1$) known symbol probabilities of the source using some properties of Kullback-Leibler distance. Since fix-free codes are special prefix-free codes (for which no codeword is a suffix of the other codewords), it is clear that all lower bounds on the redundancy of optimal prefix-free codes are also valid for fix-free ones. Accordingly, the second question of the paper is on the tightness of the derived lower bounds for optimal fix-free codes. It is proven that these lower bounds are tight for optimal fix-free codes if $j\leq 3$ , and are not tight for $j\geq 4$. Also, it is shown that the tight lower bound in terms of the probability of the most likely symbol is the same for optimal prefix-free and optimal fix-free codes. [ABSTRACT FROM AUTHOR]

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger–Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time. [ABSTRACT FROM AUTHOR]

This paper studies the Pliable Index CODing problem (PICOD), which models content-type distribution networks. In the PICOD $({t})$ problem there are ${m}$ messages, ${n}$ users and each user has a distinct message side information set, as in the classical Index Coding problem (IC). Differently from IC, where each user has a pre-specified set of messages to decode, in the PICOD $({t})$ a user is “pliable” and is satisfied if it can decode any ${t}$ messages that are not in its side information set. The goal is to find a code with the shortest length that satisfies all the users. This flexibility in determining the desired message sets makes the PICOD $({t})$ behave quite differently compared to the IC, and its analysis even more challenging. This paper mainly focuses on the complete– ${S}$ PICOD $({t})$ with ${m}$ messages, where the set ${S}\subset [{m}]$ contains the sizes of the side information sets, and the number of users is ${n}=\sum _{s\in {S}}\binom {m} {s}$ , with no two users having the same side information set. Capacity results are shown for: (i) the consecutive complete– ${S}$ PICOD $({t})$ , where ${S}=[{s}_{\text {min}}:{s}_{\text {max}}]$ for some $0 \leqslant {s}_{\text {min}}\leqslant {s}_{\text {max}} \leqslant {m}-{t}$ , and (ii) the complement-consecutive complete– ${S}$ PICOD $({t})$ , where ${S}=[0: {m}-{t}]\backslash [{s}_{\text {min}}:{s}_{\text {max}}]$ , for some $0 < {s}_{\text {min}}\leqslant {s}_{\text {max}} < {m}-{t}$. The novel converse proof is inspired by combinatorial design techniques and the key insight is to consider all messages that a user can eventually decode successfully, even those in excess of the ${t}$ required ones. This allows one to circumvent the need to consider all possible desired message set assignments at the users in order to find the one that leads to the shortest code length. The core of the novel proof is to solve the critical complete– ${S}$ PICOD $({t})$ with ${m} = 2{s}+{t}$ messages and ${S}=\{{s}\}$ , by showing the existence of a user who can decode ${s}+{t}$ messages regardless of the desired message set assignment. All other tight converse results for the complete– ${S}$ PICOD $({t})$ can be deduced from this critical case. The converse results show the information theoretic optimality of simple linear coding schemes. By similar reasoning, all complete– ${S}$ PICOD $({t})$ where the number of messages is ${m}\leqslant 5$ can be fully characterized. In addition, tight converse results are also shown for the PICOD(1) with circular-arc network topology hypergraph. [ABSTRACT FROM AUTHOR]

Locally repairable codes, or locally recoverable codes (LRC for short), are designed for applications in distributed and cloud storage systems. Similar to classical block codes, there is an important bound called the Singleton-type bound for locally repairable codes. In this paper, an optimal locally repairable code refers to a block code achieving this Singleton-type bound. Like classical MDS codes, optimal locally repairable codes carry some very nice combinatorial structures. Since the introduction of the Singleton-type bound for locally repairable codes, people have put tremendous effort into construction of optimal locally repairable codes. There are a few constructions of optimal locally repairable codes in the literature. Most of these constructions are realized via either combinatorial or algebraic structures. In this paper, we apply automorphism group of the rational function field to construct optimal locally repairable codes by considering the group action on projective lines over finite fields. Due to various subgroups of the projective general linear group, we are able to construct optimal locally repairable codes with flexible locality as well as smaller alphabet size comparable to the code length. In particular, we produce new families of $q$ -ary locally repairable codes, including codes of length $q+1$ via cyclic groups. [ABSTRACT FROM AUTHOR]

Content delivery networks store information distributed across multiple servers, so as to balance the load and avoid unrecoverable losses in case of node or disk failures. Coded caching has been shown to be a useful technique which can reduce peak traffic rates by pre-fetching popular content at the end users and encoding transmissions so that different users can extract different information from the same packet. On one hand, distributed storage limits the capability of combining content from different servers into a single message, causing performance losses in coded caching schemes. But, on the other hand, the inherent redundancy existing in distributed storage systems can be used to improve the performance of those schemes through parallelism. This paper designs coded caching and delivery schemes tailored towards systems where the library is distributed across multiple servers, possibly with some redundancy in the form of maximum distance separable (MDS) erasure codes. Different schemes are proposed based on the capacity of the users’ caches, as well as the number of parity servers. The main focus is on scenarios with one (RAID-4) or two (RAID-6) parity servers, but the paper also includes simple extensions for cases with more than two or no parity servers at all. The proposed schemes are shown to reduce the worst case latency, or equivalently the peak transmission rate from any server, below that of state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Mean hitting time for random walks on a network, defined as the average of hitting times over all possible pairs of nodes, has found a large variety of applications in many areas. In this paper, we first prove that among all $N$ -node networks, the complete graph has the minimum mean hitting time $N-1$ , which scales linearly with network size. We then study a random walk mobility model with location heterogeneity, modeled by scale-free networks, which are ubiquitous in realistic systems such as P2P networks. For this purpose, we consider random walks on two sparse scale-free small-world networks. By using the connection between random walks and electrical networks, we derive explicit formulas about mean hitting time for both networks, the dominant scaling of which exhibits the same behavior as that of complete graphs. This paper demonstrates that heterogeneous sparse networks can have low-mean hitting time with a behavior similar to that of dense complete graphs, which is instrumental in designing networks, where search is fast between any pair of nodes. [ABSTRACT FROM AUTHOR]

This paper studies the downlink of a cloud radio access network (C-RAN) in which a centralized processor (CP) communicates with mobile users through base stations (BSs) that are connected to the CP via finite-capacity fronthaul links. Information theoretically, the downlink of a C-RAN is modeled as a two-hop broadcast-relay network. Among the various transmission and relaying strategies for such model, this paper focuses on the compression strategy, in which the CP centrally encodes the signals to be broadcast jointly by the BSs, then compresses and sends these signals to the BSs through the fronthaul links. We characterize an achievable rate region for a generalized compression strategy with Marton’s multicoding for broadcasting and multivariate compression for fronthaul transmission. We then compare this rate region with the distributed decode-forward (DDF) scheme, which achieves the capacity of the general relay networks to within a constant gap, and show that the difference lies in that DDF performs Marton’s multicoding and multivariate compression jointly as opposed to successively as in the compression strategy. A main result of this paper is that under the assumption that the fronthaul links are subject to a sum capacity constraint, this difference is immaterial; so, for the Gaussian network, the compression strategy based on successive encoding can already achieve the capacity region of the C-RAN to within a constant gap, where the gap is independent of the channel parameters and the power constraints at the BSs. As a further result, for C-RAN under individual fronthaul constraints, this paper also establishes that the compression strategy can achieve to within a constant gap to the sum capacity. [ABSTRACT FROM AUTHOR]

In this paper, a general framework of constructing the optimal frequency-hopping sequence (FHS) sets is presented based on the designated direct product. Under this framework, we obtain infinitely many new optimal FHS sets by combining some one-coincide (OC) sequence sets that are newly constructed in this paper with some known optimal FHS sets. Our constructions are also based on extension method. However, our constructions give new and flexible parameters due to the free choice of OC sequence set. As a result, our constructions allow a great flexibility of choosing parameters of FHS sets for a given frequency-hopping spread spectrum system. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over $\mathbb {F}_{q}$ exists. This problem is completely solved for the case where $q$ is even. For $q$ is odd, some $q$ -ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of $q$ -ary MDS Euclidean self-dual codes by using generalized Reed–Solomon (GRS for short) codes and extended GRS codes. [ABSTRACT FROM AUTHOR]

Ovoids in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ have been an interesting topic in coding theory, combinatorics, and finite geometry for a long time. So far only two families of ovoids are known. The first is the elliptic quadrics and the second is the Tits ovoids. It is known that an ovoid in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ corresponds to a $[q^{2}+1, 4, q^{2}-q]$ code over ${\mathrm {GF}}(q)$ , which is called an ovoid code. The objectives of this paper are to develop the general theories of subfield codes and to study the subfield codes of the two families of ovoid codes. The dimensions, minimum weights, and the weight distributions of the subfield codes of the elliptic quadric codes and Tits ovoid codes are settled. The parameters of the duals of these subfield codes are also studied. Some of the codes presented in this paper are optimal, and some are distance-optimal. The parameters of the subfield codes are new. [ABSTRACT FROM AUTHOR]

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

In a paper by Guruswami et al., it was shown that the length $n$ of a $q$ -ary linear locally recoverable code with distance $d \geqslant 5$ is upper bounded by $O(dq^{3})$. Thus, it is a challenging problem to construct $q$ -ary locally recoverable codes with distance $d \geqslant 5$ and length approaching the upper bound. The same paper also gave an algorithmic construction of $q$ -ary locally recoverable codes with locality $r$ and length $n=\Omega _{r}(q^{2})$ for $d=5$ and 6, where $\Omega _{r}$ means that the implicit constant depends on locality $r$. In this paper, we present an explicit construction of $q$ -ary locally recoverable codes of distance $d= 5$ and 6 via binary constant weight codes. It turns out that 1) our construction is simpler and more explicit and 2) the length of our codes is greater than previously known. [ABSTRACT FROM AUTHOR]

This paper examines the average age minimization problem where only a fraction of the network users can transmit simultaneously over unreliable channels. Finding the optimal scheduling scheme, in this case, is known to be challenging. Accordingly, the Whittle’s index policy was proposed in the literature as a low-complexity heuristic to the problem. Although simple to implement, characterizing this policy’s performance is recognized to be a notoriously tricky task. In the sequel, we provide a new mathematical approach to establish its optimality in the many-users regime for specific network settings. Contrary to previous works in the literature that use restrictive mathematical assumptions, which can be challenging to verify, our novel approach is based on intricate techniques and it is free of any strong mathematical assumptions. These findings showcase that the Whittle’s index policy has analytically provable asymptotic optimality for the AoI minimization problem. Finally, we lay out numerical results that corroborate our theoretical findings and demonstrate the policy’s notable performance in the many-users regime. [ABSTRACT FROM AUTHOR]

The zero capacity region for hexagonal $(d,k)$ run-length constraints is known for many, but not all, $d$ and $k$. The pairs $(d,k)$ for which it has been unproven whether the capacity is zero or positive consist of: (i) $k=d+2$ when $d\ge 2$ ; (ii) $k=d+3$ when $d \ge 1$ ; (iii) $k=d+4$ when either $d=4$ or $d$ is odd and $d \ge 3$ ; and (iv) $k=d+5$ when $d=4$. Here, we prove that the capacity is zero for all of case (i), and for case (ii) whenever $d \ge 7$. The method used in this paper is to reduce an infinite search space of valid labelings to a finite set of configurations that we exhaustively examine using backtracking. In Part II of this two-part series, we use automated procedures to prove that the capacity is zero in case (i) when $2 \le d \le 9$ , in case (ii) when $3 \le d \le 11$ , and in case (iii) when $d \in \{ 4,5,7,9 \}$ , and that the capacity is positive in case (ii) when $d \in \{1,2\}$ , in case (iii) when $d = 3$ , and in case (iv). Thus, the only remaining unknown cases are now when $k=d+4$ , for any odd $d \ge 11$. [ABSTRACT FROM AUTHOR]

This paper proposes a new method of constructing compact fully-connected Quasi-Cyclic Low Density Parity Check (QC-LDPC) codes with girth $g$ = 8, 10, and 12. The originality of the proposed method is to impose constraints on the exponent matrix P to reduce the search space drastically. For a targeted lifting degree of $N$ , the first step of the method is to sieve the integer ring $\mathbb {Z}_{N}$ to make a particular sub-group with specific properties to construct the second column of P (the first column being filled with zeros). The remaining columns of P are determined recursively as multiples of the second column by adapting the sequentially multiplied column (SMC) method whereby a controlled greedy search is applied at each step. The codes constructed with the proposed semi-algebraic method show lengths that can be significantly shorter than their best counterparts in the literature. [ABSTRACT FROM AUTHOR]

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Luby et al. Both sequences are provably capacity-achieving under belief propagation decoding when transmission takes place over the binary erasure channel. In this paper we show that many existing capacity-achieving sequences of low-density parity-check codes are not universal under belief propagation decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of low-density parity-check code ensembles, we determine a stability threshold associated with them, which gives rise to a sufficient condition under which the sequence is not universal under belief propagation decoding. Moreover, we show that the same stability threshold applies to blockwise or bitwise maximum a posteriori decoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, revealing the operational significance of the stability threshold. [ABSTRACT FROM AUTHOR]

Consider a massive random access scenario in which a small set of $k$ active users out of a large number of $n$ potential users need to be scheduled in $b\ge k$ slots. What is the minimum common feedback to the users needed to ensure that scheduling is collision-free? Instead of a naive scheme of listing the indices of the $k$ active users in the order in which they should transmit, at a cost of $k\log (n)$ bits, this paper shows that for the case of $b=k$ , the rate of the minimum fixed-length common feedback code scales only as $k \log (e)$ bits, plus an additive term that scales in $n$ as $\Theta (\log \log (n))$ for fixed $k$. If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires $k \log (e)$ bits, but the dependence on $n$ can be reduced to $O(1)$. When $b>k$ , the number of feedback bits needed for collision-free scheduling can be significantly further reduced. Moreover, a similar scaling on the minimum feedback rate is derived for the case of scheduling $m$ users per slot, when $k \le mb$. The problem of constructing a minimum collision-free feedback scheduling code is connected to that of constructing a perfect hashing family, which allows practical feedback scheduling codes to be constructed from perfect hashing algorithms. [ABSTRACT FROM AUTHOR]

A complete characterization for the restricted isometry constant (RIC) bounds on $\delta _{{{ tk}}}$ for all $ {t}>0$ is an important problem on recovery of sparse signals with prior support information via weighted $\ell _{{p}}$ -minimization ($0 < {p} \leqslant 1$). In this paper, new bounds on the restricted isometry constants $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$), where $d$ is a key constant determined by prior support information, are established to guarantee the sparse signal recovery via the weighted $\ell _{{p}}$ minimization in both noiseless and noisy settings. This result fills a vacancy on $\delta _{{{ tk}}}$ with $0 < {t} < \frac {4}{3}{d}$ , compared with previous works on $\delta _{{{ tk}}}$ (${t} \geqslant \frac {4}3{d}$). We show that, when the accuracy of prior support estimate is at least 50%, the new recovery condition in terms of $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$) via weighted $\ell _{1}$ minimization is weaker than the condition required by classical $\ell _{1}$ minimization without weighting. Our weighted $\ell _{1}$ minimization gives better recovery error bounds in noisy setting. Similarly, the new recovery condition in terms of $\delta _{{{ tk}}}$ ($0 < {t} < \frac {4}{3}{d}$) is extended to weighted $\ell _{{p}}$ ($0 < {p} < 1$) minimization, and it is also weaker than the condition obtained by standard non-convex $\ell _{{p}}$ ($0 < {p} < 1$) minimization without weighting. Numerical illustrations are provided to demonstrate our new theoretical results. [ABSTRACT FROM AUTHOR]

The paper deals with linear information inequalities valid for entropy functions induced by discrete random variables. Specifically, the so-called conditional Ingleton inequalities are in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. We discuss five inequalities of this particular type, four of which has appeared earlier in the literature. Besides the proof of the new fifth inequality, simpler proofs of (some of) former inequalities are presented. These five information inequalities are used to characterize all conditional independence structures induced by four discrete random variables. [ABSTRACT FROM AUTHOR]