Search

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes. [ABSTRACT FROM AUTHOR]

This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22. [ABSTRACT FROM AUTHOR]

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

A common method for reading information stored in DNA molecules is shotgun sequencing. This method outputs a histogram of the frequencies of all the molecules’ substrings of a given length $\ell $. To protect against noisy readings, the rank-modulation scheme encodes the information in the relative ranking of the substring frequencies, instead of their absolute values. However, the best rank-modulation codes for shotgun sequencing have low rates which are asymptotically vanishing. In this paper we propose new constructions of rank-modulation codes for shotgun sequencing. The first code construction is systematic, allowing the user to arbitrarily set the frequencies of a large subset of the substrings, which the encoder then completes to a permutation that may be realized by a DNA molecule. The construction is then improved by allowing the user to set the frequencies of additional substrings, at the cost of imposing constraints on the frequencies. The resulting codes have higher, non-vanishing rates, compared with previously known codes. As an example, for histograms of substrings of length $\ell =2$ , and an alphabet of size 4 (as in DNA molecules), we are able to construct a code with rate $\approx 0.909$ , whereas previously, the best construction resulted in a code with rate $\approx 0.654$. Additionally, the encoded information in our construction may be written to shorter DNA molecules than possible before. We also prove that the systematic codes constructed in this paper are the largest possible among all systematic codes. [ABSTRACT FROM AUTHOR]

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $\tau \ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $\tau < 1$ and $n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes. [ABSTRACT FROM AUTHOR]

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta $ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta $ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$ , and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$ ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

The notion of correlation immune functions has been introduced by Siegenthaler (1984) in symmetric cryptography in the framework of stream ciphers. At the conference CRYPTO’91 by Camion et al., it has been pointed out that this notion existed in statistics and combinatorics. It has recently been highlighted that such functions also play an important role in a new framework related to side-channel attack counter-measures. Since then, the interest in correlation immune Boolean functions has been renewed, and new challenges regarding these functions have appeared. Specifically, low Hamming weight correlation immune functions have been selected as useful for counter-measures to side-channel attacks. Despite their importance, the literature is not abundant in this research direction. Two very interesting articles in which such correlation immune functions were nicely explored, given this novel use of them. Carlet initiated the first one in 2013, and the second one is due to Carlet and Chen (2018). This paper deals with correlation immune Boolean functions aiming to produce more candidates of those processing low Hamming weights. We shall focus on correlation immune Boolean functions with Hamming weights power of 2 (which offer a flexibility to control the correlation immunity aspects) and present several methods of designing them. Some design methods are efficient and could be employed to derive such functions. Consequently, given two positive integers $n$ and $m$ , we derive new effective constructions of correlation immune Boolean functions with Hamming weight power of 2. Furthermore, an upper bound on the correlation immunity of the newly constructed $n$ -variable Boolean functions with Hamming weight $2^{m}$ was determined for $n-m\ge 0$. Besides, exact values and lower bounds on the maximum correlation immunity of those functions are explored and discussed, mainly when the values of $n$ and $m$ are very close. This paper also exhibits explicit examples of those correlation immune functions that illustrate our methods. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

This paper studies low-latency streaming codes for the multi-hop network. The source transmits a sequence of messages to a destination through a chain of relays, and requires the destination to reconstruct each message by its deadline. We assume that each communication link is subjected to a certain maximum number of packet erasures. The case of a single relay (a three-node network) was considered in Fong et al. (2020). A coding scheme known as symbol-wise decode and forward was proposed. In the present work, we propose an alternative scheme that is different from Fong et al. (2020) and still achieves the same rate as in Fong et al. (2020) for the one hop case as the field-size goes to infinity. Furthermore, our proposed scheme naturally generalizes to the case of multiple-relay nodes yielding new achievable rates for this setting. The main difference with Fong et al. (2020) is that our proposed scheme exploits the ability of the relay nodes to adapt the transmission based on the erasures on the previous link. Hence, we refer to our scheme as “state-dependent” and contrast it with the scheme in Fong et al. (2020) that is state-independent. Our scheme requires the relay nodes to append a header to the transmitted packets, and we show that the size of the header does not depend on the field-size of the code. We also derive an upper bound on the maximal streaming rate achievable over a network with an arbitrary number of relays. We show that this upper bound matches our achievable rate in the special case when the maximal number of erasures on the first link is greater than or equal to the maximal number of erasures on each of the following links, and the field size goes to infinity. [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]

This paper investigates the secret key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Prior to the encoder’s transmission, the adversary decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the adversary’s objective being to have the decoder accept and decode their observation to a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret key-authenticated-capacity region is defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the second of a two-part study, with the parts differing in their measure of the authentication rate. For this second study, the probability of false authentication is considered as a function of the system state, where the system state is defined by the message being transmitted, the value of the secret key, the adversary’s channel observations, and the adversary’s (possibly stochastic) choice for the decoder’s observation. Termed the typical-authentication rate, the authentication measure considered here corresponds to an upper bound on the probability of false authentication for the majority of system states. For this measure, we derive matching inner and outer bounds for the secret key-enabled authenticated capacity region in terms of traditional information-theoretic measures. In doing so, it is shown that the typical-authentication rate and the message rate exhibit a one-to-one trade-off in the capacity region. [ABSTRACT FROM AUTHOR]

The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet $\Sigma $. The theorem asserts that, for any such sequence $S$ , the following two things are true. (1) If $S$ is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in $S$), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on $S$. (2) If $S$ is normal, then any finite-state gambler loses money at an exponential rate betting on $S$. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence ${\mathrm {div}}(S||\alpha)$ of a probability measure $\alpha $ on $\Sigma $ from a sequence $S$ over $\Sigma $ and the upper asymptotic divergence ${\mathrm {Div}}(S||\alpha)$ of $\alpha $ from $S$ in such a way that a sequence $S$ is $\alpha $ -normal (meaning that every string $w$ has asymptotic frequency $\alpha (w)$ in $S$) if and only if ${\mathrm {Div}}(S||\alpha)=0$. We also use the Kullback-Leibler divergence to quantify the total risk ${\mathrm {Risk}}_{G}(w)$ that a finite-state gambler $G$ takes when betting along a prefix $w$ of $S$. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to $\alpha $ -normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes $w$ of $S$. ($1~'$) The infinitely-often exponential rate of winning in 1 is $2^{{\mathrm {Div}}(S||\alpha)|w|}$. ($2~'$) The exponential rate of loss in 2 is $2^{- {\mathrm {Risk}}_{G}(w)}$. We also use (1 $'$) to show that $1- {\mathrm {Div}}(S||\alpha)/c$ , where $c= \log (1/ \min _{a\in \Sigma }\alpha (a))$ , is an upper bound on the finite-state $\alpha $ -dimension of $S$ and prove the dual fact that $1- {\mathrm {div}}(S||\alpha)/c$ is an upper bound on the finite-state strong $\alpha $ -dimension of $S$. [ABSTRACT FROM AUTHOR]

Self-orthogonal codes are an important type of linear codes due to their wide applications in communication and cryptography. The Euclidean (or Hermitian) hull of a linear code is defined to be the intersection of the code and its Euclidean (or Hermitian) dual. It is clear that the hull is self-orthogonal. The main goal of this paper is to obtain self-orthogonal codes by investigating the hulls. Let $\mathcal {C}_{(r,r^{m}-1,\delta,b)}$ be the primitive BCH code over $\mathbb {F}_{r}$ of length $r^{m}-1$ with designed distance $\delta $ , where $\mathbb {F}_{r}$ is the finite field of order $r$. In this paper, we will present Euclidean (or Hermitian) self-orthogonal codes and determine their parameters by investigating the Euclidean (or Hermitian) hulls of some primitive BCH codes. Several sufficient and necessary conditions for primitive BCH codes with large Hermitian hulls are developed by presenting lower and upper bounds on their designed distances. Furthermore, some Hermitian self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated. In addition, we determine the dimensions of the code $\mathcal {C}_{(r,r^{2}-1,\delta,1)}$ and its hull in both Hermitian and Euclidean cases for $2 \le \delta \le r^{2}-1$. We also present two sufficient and necessary conditions on designed distances such that the hull has the largest dimension. [ABSTRACT FROM AUTHOR]

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties. [ABSTRACT FROM AUTHOR]

We investigate the state-dependent Gaussian wiretap channel with noncausal channel state information at the transmitter (GWTC-N-CSIT), and explore whether three strategies (i.e., taking action on the state, legitimate receiver’s channel output feedback, and combining the former two strategies together) help to enhance the secrecy capacity of the GWTC-N-CSIT. To be specific, we first determine the secrecy capacity of the GWTC-N-CSIT with noiseless feedback. Next, we derive lower and upper bounds on the secrecy capacity of the GWTC-N-CSIT with action-dependent state. Finally, we derive lower and upper bounds on the secrecy capacity of the GWTC-N-CSIT with both action-dependent state and noiseless feedback, and show that these bounds meet for a special case. Numerical results of this paper indicate that all three strategies enhance the secrecy capacity of the GWTC-N-CSIT. The study of this paper offers new options for enhancing the secrecy rates of the state-dependent wiretap channel models. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

All-or-nothing transforms (AONTs) were proposed by Rivest as a message preprocessing technique for encrypting data to protect against brute-force attacks, and have numerous applications in cryptography and information security. Later the unconditionally secure AONTs and their combinatorial characterization were introduced by Stinson. Informally, a combinatorial AONT is an array with the unbiased requirements and its security properties in general depend on the prior probability distribution on the inputs $s$ -tuples. Recently, it was shown by Esfahani and Stinson that a combinatorial AONT has perfect security provided that all the inputs $s$ -tuples are equiprobable, and has weak security provided that all the inputs $s$ -tuples are with non-zero probability. This paper aims to explore on the gap between perfect security and weak security for combinatorial $(t,s,v)$ -AONTs. Concretely, we consider the typical scenario that all the $s$ inputs take values independently (but not necessarily identically) and quantify the amount of information $H(\mathcal {X}|\mathcal {Y})$ about any $t$ inputs $\mathcal {X}$ that is not revealed by any $s-t$ outputs $\mathcal {Y}$. In particular, we establish the general lower and upper bounds on $H(\mathcal {X}|\mathcal {Y})$ for combinatorial AONTs using information-theoretic techniques, and also show that the derived bounds can be attained in certain cases. Furthermore, the discussions are extended for the security properties of combinatorial asymmetric AONTs. [ABSTRACT FROM AUTHOR]

In ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of $2 q$ tuples of $n$ -bit strings $(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda _{i}$ for $1 \leq i \leq q$ such that $P_{1}, P_{2}, \ldots $ , $P_{2q}$ are distinct and $\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known as Mirror theory and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory. [ABSTRACT FROM AUTHOR]

Live communication is ubiquitous, and frequently must contend with reliability issues due to packet loss during transmission. The effect of packet losses can be alleviated by using erasure codes, which aid in recovering lost packets. Streaming codes are a class of codes designed for the live communication setting, which encode a stream of message packets arriving sequentially for transmission over a packet-loss channel. The existing study of streaming codes considers settings where the sizes of the message packets to be transmitted are all fixed. However, message packets occur with unpredictable and variable sizes in many applications, such as videoconferencing. In this paper, we present a generalized model for streaming codes that incorporates message packets of variable sizes. We show that the variability in the sizes of message packets induces a new trade-off between the rate and the decoding delay under lossless transmission. Moreover, the variability in the sizes of message packets impacts the optimal rate of transmission. To address this, we introduce algorithms to compute upper and lower bounds on the optimal rate for any given sequence of sizes of message packets. We then design an explicit streaming code for the proposed model. We empirically evaluate the code construction over a live video trace for several representative parameter settings, and show that the rate of the construction is approximately 90% of an upper bound and 5%–48% higher than naively using the existing streaming codes. [ABSTRACT FROM AUTHOR]

Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in high-speed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over $\mathbb {F}_{M}$ of $M$ -ary Sidelnikov sequence of period $q-1$ using Hasse derivative, which implies $q=p^{m}$ , $m\geq 1$ and $M|(q-1)$. The $t$ th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for $M=2$ and 3 are obtained only with some additional restrictions on $q$. Furthermore, concrete illustrations for several families of these sequences, such as $q\equiv 1\pmod {2}$ and $q\equiv 1\pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2\times 3^{\lambda }+1 (1\leq \lambda \leq 20)$ , the exact linear complexities over $\mathbb {F}_{3}$ of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods. [ABSTRACT FROM AUTHOR]

The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $r\geq 3$ be a positive integer satisfying $\gcd (r,n)=1$ and $\gcd \big (r,q(q^{2}-1)\big)=1$. We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$. [ABSTRACT FROM AUTHOR]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

In this paper we prove several coordinate-ordering-free upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraic-geometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of Reed-Muller codes with the special coordinate ordering is also given. [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]

The strong secrecy transmission problem of the arbitrarily varying wiretap channel (AVWC) with input and state constraints is investigated in this paper. First, a stochastic-encoder code lower bound of the strong secrecy capacity is established by applying the type argument and Csiszár’s almost independent coloring lemma. Then, a superposition stochastic-encoder code lower bound of the secrecy capacity is provided. The superposition stochastic-encoder code lower bound can be larger than the ordinary stochastic-encoder code lower bound. Random code lower and upper bounds of the secrecy capacity of the AVWC with constraints are further provided. Based on these results, we further consider a special case of the model, namely severely less noisy AVWC, and give the stochastic-encoder code and random code capacities. It is proved that the stochastic-encoder code capacity of the AVWC with constraints is either equal to or strictly smaller than the corresponding random code capacity, which is consistent with the property of the ordinary AVC. Finally, some numerical examples are presented to better illustrate our capacity results. Compared to the soft covering lemma that requires the codewords to be generated i.i.d., our method has more relaxed requirements regarding codebooks. It is proved that the good codebooks for secure transmission can be generated by choosing codewords randomly from a given type set, which is critical when considering the AVWC with constraints. [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]

A block code is called a locally recoverable code (LRC for short) with $(r,\delta)$ -locality, if subject to any $\delta -1$ erasure failures, every symbol in the encoding can still be recovered by accessing at most $r$ other symbols. Recently, it was discovered by several authors that a $q$ -ary optimal $(r,\delta)$ -LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$ -ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special cases). In this paper, we further investigate constructions of optimal $(r,\delta)$ -LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of $\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal $(r,\delta)$ -LRC with code length $\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ , where $d$ is the minimum distance. In particular, to our surprise, for $\delta =2$ this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami et al. (2018) for $d\geq 7$. In addition, for $d=6$ , we are able to remove the constraint required in Jin (2019) that $q$ is even. [ABSTRACT FROM AUTHOR]

One of the important unsolved problems in information theory is the conjecture that the undirected multiple-unicast network information capacity is the same as the routing capacity. This conjecture is verified only for a handful of networks and network classes. Moreover, only two explicit upper bounds on information capacity are known for general undirected networks: the sparsest cut bound and the linear programming bound. In this paper, we present an information-theoretic upper bound, called the partition bound, on the capacity of general undirected multiple-unicast networks. We show that a decision version problem of computing the bound is NP-complete. We present two classes of undirected multiple-unicast networks such that the partition bound is achievable by routing. Thus, the conjecture is proved for these classes of networks. Recently, the conjecture was proved for a new class of networks defined by properties relating to cut-set and source-sink paths. We show the existence of a network outside of this new class of networks such that the partition bound is achievable by routing. [ABSTRACT FROM AUTHOR]

Insertion–deletion codes (insdel codes for short) play an important role in synchronization error correction. The higher the minimum insdel distance, the more insdel errors the code can correct. Haeupler and Shahrasbi established the Singleton bound for insdel codes: the minimum insdel distance of any $[n,k]$ linear code over $\mathbb {F}_{q}$ satisfies $d\leq 2n-2k+2$. There have been some constructions of insdel codes through Reed-Solomon codes with high capabilities, but none has come close to this bound. Recently, Do Duc et al. showed that the minimum insdel distance of any $[n,k]$ Reed-Solomon code is no more than $2n-2k$ if $q$ is large enough compared to the code length $n$ ; optimal codes that meet the new bound were also constructed explicitly. The contribution of this paper is twofold. We first show that the minimum insdel distance of any $[n,k]$ linear code over $\mathbb {F}_{q}$ satisfies $d\leq 2n-2k$ if $n > k > 1$. This result improves and generalizes the previously known results in the literature. We then give a sufficient condition under which the minimum insdel distance of a 2-D Reed-Solomon code of length $n$ over $\mathbb {F}_{q}$ is exactly equal to $2n-4$. As a consequence, we show that the sufficient condition is not hard to achieve; we explicitly construct an infinite family of optimal 2-D Reed-Somolom codes meeting the bound. [ABSTRACT FROM AUTHOR]

Due to wide applications of binary sequences with a low correlation to communications, various constructions of such sequences have been proposed in the literature. Many efforts have been made to construct good binary sequences with various lengths. However, most of the known constructions make use of the multiplicative cyclic group structure of finite field $\mathbb {F}_{2^{n}}$ for a positive integer $n$. It is often overlooked in this community that all $2^{n}+1$ rational places (including “the place at infinity”) of the rational function field over $\mathbb {F}_{2^{n}}$ form a cyclic structure under an automorphism of order $2^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length $2^{n}+1$ via cyclotomic function fields over $\mathbb {F}_{2^{n}}$. Each family of our sequences has size $2^{n}-1$ and its correlation is upper bounded by $\lfloor 2^{(n+2)/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length $2^{n}+1$. Moreover, our sequences can be constructed explicitly and have competitive parameters. In particular, compared with the Gold sequences of length $2^{n}-1$ for even $n$ , our sequences have a smaller correlation and a larger length although the family size of our sequences is slightly smaller. [ABSTRACT FROM AUTHOR]

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and has numerous practical applications. One of the defining features of group testing is whether the tests are adaptive (i.e., a given test can be chosen based on all previous outcomes) or non-adaptive (i.e., all tests must be chosen in advance). In this paper, building on the success of binary splitting techniques in noiseless group testing (Hwang, 1972), we introduce noisy group testing algorithms that apply noisy binary search as a subroutine. We provide three variations of this approach with increasing complexity, culminating in an algorithm that succeeds using a number of tests that matches the best known previously (Scarlett, 2019), while overcoming fundamental practical limitations of the existing approach, and more precisely capturing the dependence of the number of tests on the error probability. We provide numerical experiments demonstrating that adaptive group testing strategies based on noisy binary search can be highly effective in practice, using significantly fewer tests compared to state-of-the-art non-adaptive strategies. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

A general class of Bayesian lower bounds when the underlying loss function is a Bregman divergence is demonstrated. This class can be considered as an extension of the Weinstein–Weiss family of bounds for the mean squared error and relies on finding a variational characterization of Bayesian risk. This approach allows for the derivation of a version of the Cramér–Rao bound that is specific to a given Bregman divergence. This new generalization of the Cramér–Rao bound reduces to the classical one when the loss function is taken to be the Euclidean norm. In order to evaluate the effectiveness of the new lower bounds, the paper also develops upper bounds on Bayesian risk, which are based on optimal linear estimators. The effectiveness of the new bound is evaluated in the Poisson noise setting. [ABSTRACT FROM AUTHOR]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$ -element Galois field which is linear in both $q$ and $k$ , hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multi-hop path of $N$ relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD $N$ -relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the $N+1$ listen/transmit states (out of the $2^{N}$ possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed. [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]

Let $\mathbb {F}_{q}$ be the finite field of $q$ elements. In this paper we obtain bounds on the following counting problem: given a polynomial $f(x)\in \mathbb {F}_{q} [x]$ of degree $k+m$ and a non-negative integer $r$ , count the number of polynomials $g(x)\in \mathbb {F}_{q} [x]$ of degree at most $k-1$ such that $f(x)+g(x)$ has exactly $r$ roots in $\mathbb {F}_{q}$. Previously, explicit formulas were known only for the cases $m=0, 1, 2$. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code $[q, k, q-k+1]_{q}$. [ABSTRACT FROM AUTHOR]

This paper studies an $n$ -dimensional additive Gaussian noise channel with a peak-power-constrained input. It is well known that, in this case, when $n=1$ the capacity-achieving input distribution is discrete with finitely many mass points, and when $n>1$ the capacity-achieving input distribution is supported on finitely many concentric shells. However, due to the previous proof technique, not even a bound on the exact number of mass points/shells was available. This paper provides an alternative proof of the finiteness of the number mass points/shells of the capacity-achieving input distribution while producing the first firm bounds on the number of mass points and shells, paving an alternative way for approaching many such problems. The first main result of this paper is an order tight implicit bound which shows that the number of mass points in the capacity-achieving input distribution is within a factor of two from the number of zeros of the downward shifted capacity-achieving output probability density function. Next, this implicit bound is utilized to provide a first firm upper on the support size of optimal input distribution, an $O(\mathsf {A}^{2})$ upper bound where $\mathsf {A}$ denotes the constraint on the input amplitude. The second main result of this paper generalizes the first one to the case when $n>1$ , showing that, for each and every dimension $n\ge 1$ , the number of shells that the optimal input distribution contains is $O(\mathsf {A}^{2})$. Finally, the third main result of this paper reconsiders the case $n=1$ with an additional average power constraint, demonstrating a similar $O(\mathsf {A}^{2})$ bound. [ABSTRACT FROM AUTHOR]

Given a ${q}$ -ary frequency hopping sequence set of length ${n}$ and size ${M}$ with Hamming correlation ${H}$ , one can obtain a ${q}$ -ary (nonlinear) cyclic code of length ${n}$ and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool–martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region. [ABSTRACT FROM AUTHOR]

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/s)$ of the bits of the database; here $s$ is a fixed rational number with $s > 1$. A PIR array code with the $k$ -PIR property enables a $k$ -server PIR protocol (with $k\leq m$) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$ , is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$ -PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when $1 < s \leq 2$. A $k$ -PIR code (and similarly a $k$ -PIR array code) is also a locally repairable code with symbol availability $k-1$. Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role. [ABSTRACT FROM AUTHOR]

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources. [ABSTRACT FROM AUTHOR]

In 2007, Carlet and Ding introduced two parameters, denoted by $Nb_{F}$ and $NB_{F}$ , quantifying respectively the balancedness of general functions $F$ between finite Abelian groups and the (global) balancedness of their derivatives $D_{a} F(x)=F(x+a)-F(x)$ , $a\in G\setminus \{0\}$ (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided inequalities relating the nonlinearity $\mathcal {NL}(F)$ to $NB_{F}$ for S-box and specifically obtained an upper bound on the nonlinearity that unifies Sidelnikov-Chabaud-Vaudenay’s bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions $F+L$ , where $L$ is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario et al. for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives, respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without comparing the second pair of parameters to the first one. In this paper, we observe that ambiguity is the same parameter as $NB_{F}$ up to additive and multiplicative constants (i.e., up to rescaling). We perform the necessary work of comparison and unification of the results on $NB_{F}$ and on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any finite Abelian groups. More importantly, we derive many new results on these parameters. [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]

This paper derives upper and lower bounds on the secrecy capacity-memory tradeoff of a wiretap erasure broadcast channel (BC) with ${\mathsf{K}}_{w} $ weak receivers and ${\mathsf {K}}_{s} $ strong receivers, where weak receivers and strong receivers have the same erasure probabilities and cache sizes, respectively. The lower bounds are achieved by the schemes that meticulously combine joint cache-channel coding with wiretap coding and key-aided one-time pads. The presented upper bound holds more generally for arbitrary degraded BCs and arbitrary cache sizes. When only weak receivers have cache memories, upper and lower bounds coincide for small and large cache memories, thus providing the exact secrecy capacity-memory tradeoff for this setup. The derived bounds further allow us to conclude that the secrecy capacity is positive even when the eavesdropper is stronger than all the legitimate receivers with cache memories. Moreover, they show that the secrecy capacity-memory tradeoff can be significantly smaller than its non-secure counterpart, but it grows much faster when cache memories are small. This paper also presents a lower bound on the global secrecy capacity-memory tradeoff where one is allowed to optimize the cache assignment subject to a total cache budget. It is close to the best known lower bound without secrecy constraint. For small total cache budget, the global secrecy capacity-memory tradeoff is achieved by assigning all the available cache memory uniformly over all the receivers if the eavesdropper is stronger than all the legitimate receivers, and it is achieved by assigning the cache memory uniformly only over the weak receivers if the eavesdropper is weaker than the strong receivers. [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]