Search

The article announces 2015 IEEE Information Theory Society Paper Award given to Itzhak Tamo and Alexander Barg for the paper "A Family of Optimal Locally Recoverable Codes."

The article offers information on the 2015 IEEE Communications Society and Information Theory Society Joint Paper Awards given to Mohammad Ali Maddah-Ali and David Tse for the paper "Completely Stale Transmitter Channel State Information is Still Very Useful."

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]

This paper aims to characterize the capacity limits of a wireless cellular network with a full-duplex (FD) base-station (BS) and half-duplex user terminals, in which three independent messages are communicated: the uplink message m1 from the uplink user to the BS, the downlink message m2 from the BS to the downlink user, and the device-to-device (D2D) message m3 from the uplink user to the downlink user. From an information theoretical perspective, the overall network can be viewed as a generalization of the FD relay broadcast channel with a side message transmitted from the relay to the destination. We begin with a simpler case that involves the uplink and downlink transmissions of (m1, m2) only, and propose an achievable rate region based on a novel strategy that uses the BS as a FD relay to facilitate the interference cancellation at the downlink user. We also prove a new converse, which is strictly tighter than the cut-set bound, and characterize the capacity region of the scalar Gaussian FD network without a D2D message to within a constant gap. This paper further studies a general setup wherein (m1, m2, m3) are communicated simultaneously. To account for the D2D message, we incorporate Marton’s broadcast coding into the previous scheme to obtain a larger achievable rate region than the existing ones in the literature. We also improve the cut-set bound by means of genie and show that by using one of the two simple rate-splitting schemes, the capacity region of the scalar Gaussian FD network with a D2D message can already be reached to within a constant gap. Finally, a generalization to the vector Gaussian channel case is discussed. Simulation results demonstrate the advantage of using the BS as relay in enhancing the throughput of the FD cellular network. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to the problem of recovering a signal $ {x}_{\star }\in \mathbb {C}^{n}$ from its phaseless measurements $\text {y}_{\text {i}}=| {a}_{i}^{ \mathsf {H}} {x}_{\star }|$ , where $\{ {a}_{\text {i}}\}_{\text {i}=1}^{ {m}}$ are the measurement vectors. Spectral method is widely used for initialization in many phase retrieval algorithms. The quality of spectral initialization can have a major impact on the overall algorithm. In this paper, we focus on the model where $ {A}=[ {a}_{1},\ldots, {a}_{ {m}}]^{ \mathsf {H}}$ has orthonormal columns, and study the spectral initialization under the asymptotic setting $ {m}, {n}\to \infty $ with $ {m}/ {n}\to \delta \in (1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: 1) There exists a threshold on $\delta $ (denoted as $\delta _{ \mathrm {weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that $\delta _{ \mathrm {weak}}=2$ for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that $\delta _{ \mathrm {weak}}=1$ for the i.i.d. Gaussian model. 2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu. [ABSTRACT FROM AUTHOR]

This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, otherwise no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main contributions in this paper include: (a) the development of a constant gap approximation for the unicast and multicast capacities of the proposed network model, i.e., a characterization of the network unicast and multicast capacities to within an additive gap, which only depends on the number of nodes and is independent of the channel coefficients and operating SNR; and (b) the design of algorithms that run in polynomial time in the number of nodes and compute the approximate unicast and multicast capacities, as well as their corresponding optimal beam scheduling strategies. These results are derived both for full-duplex and half-duplex modes of operation at the relays: while in full-duplex the transmit and receive beams at a relay can be simultaneously active, in half-duplex only one can be active at each point in time. The relation between the approximate multicast capacity and minimum unicast capacity is explored in full-duplex 1-2-1 networks and shown to be dependent on the network structure and the number of destinations, unlike in classical wireless (i.e., without 1-2-1 constraints) full-duplex networks. Finally, network simplification results are proved for the 1-2-1 network model by exploiting the structure of the linear program that represents the approximate capacity. [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]

In this paper, we construct four families of linear codes over finite fields from the complements of either the union of subfields or the union of cosets of a subfield, which can produce infinite families of optimal linear codes, including infinite families of (near) Griesmer codes. We also characterize the optimality of these four families of linear codes with an explicit computable criterion using the Griesmer bound and obtain many distance-optimal linear codes. In addition, by a more in-depth discussion on some special cases of these four families of linear codes, we obtain several classes of (distance-)optimal linear codes with few weights and completely determine their weight distributions. It is shown that most of our linear codes are self-orthogonal or minimal which are useful in applications. [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]

Quantum readout provides a general framework for formulating statistical discrimination of quantum channels. Several paths have been taken for such this problem. However, there is much to be done in the avenue of optimizing channel discrimination using classical codes. At least two open questions can be pointed out: how to construct low complexity encoding schemes that are interesting for channel discrimination and, more importantly, how to develop capacity-achieving protocols. This paper aims at presenting a solution to these questions using polar codes. Firstly, we characterize the information rate and reliability parameter of the channels under polar encoding. We also show that the error probability of the scheme proposed decays exponentially with the square root of the code length. Secondly, an analysis of the optimal quantum states to be used as probes is given. [ABSTRACT FROM AUTHOR]

A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The tension between the description rate and the exponential growth rate of the power mean of the required number of guesses is quantified. This can be viewed as the guessing version of the classical indirect-rate-distortion problem of Dobrushin-Tsybakov’62 and Witsenhausen’80. Judicious choices of the correlated sequence, the description rate, and the fidelity criterion recover a number of recent and classical results on guessing. In the context of security, the paper provides conservative estimates on a password’s remaining security after a number of bits from a correlated database have been leaked. [ABSTRACT FROM AUTHOR]

In real life we often deal with independent but not identically distributed observations (i.n.i.d.o), for which the most well-known statistical model is the multiple linear regression model (MLRM) with non-random covariates. While the classical methods are based on the maximum likelihood estimator (MLE), it is well known its lack of robustness to small deviations from the assumed conditions. In this paper, and based on the Rényi’s pseudodistance (RP), we introduce a new family of estimators in case our information about the unknown parameter is given for i.n.i.d.o.. This family of estimators, let us say minimum RP estimators (as they are obtained by minimizing the RP between the assumed distribution and the empirical distribution of the data), contains the MLE as a particular case and can be applied, among others, to the MLRM with non-random covariates. Based on these estimators, we introduce Wald-type tests for testing simple and composite null hypotheses, as an extension of the classical MLE-based Wald test. Influence functions for the estimators and Wald-type tests are also obtained and analysed. Finally, a simulation study is developed in order to asses the performance of the proposed methods and some real-life data are analysed for illustrative purpose. [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]

In this paper, we introduce the concept of biprojectivity in studying the cryptographically important almost perfect nonlinear (APN) functions. Although several known families of biprojective APN functions exist in the literature, the concept itself has not been explicitly observed and studied in detail. We give a survey of known APN families and functions that fall into the biprojective setting, then provide a method for finding such families and functions. We finally give two new infinite families of biprojective APN functions ${\mathsf {CCZ}}$ -inequivalent to any known APN function and study their properties. [ABSTRACT FROM AUTHOR]

Linear codes over $\mathbb {Z}_{p^{s}}$ of length $n$ are subgroups of $\mathbb {Z}_{p^{s}}^{n}$. These codes are also called $\mathbb {Z}_{p^{s}}$ -additive codes and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{p^{s}}$ -linear code is a code over $\mathbb {Z}_{p}$ , not necessarily linear, which is the generalized Gray map image of a $\mathbb {Z}_{p^{s}}$ -additive code. In 2015, a systematic encoding was found for $\mathbb {Z}_{4}$ -linear codes. Moreover, an alternative permutation decoding method, which is suitable for any binary code (not necessarily linear) with a systematic encoding, was established. In this paper, we generalize these results by presenting a systematic encoding for any $\mathbb {Z}_{p^{s}}$ -linear code with $s\geq 2$ and $p$ prime. We also describe a permutation decoding method for any systematic code over $\mathbb {Z}_{p}$ , not necessarily linear, and show some examples of how to use this systematic encoding in this decoding method. [ABSTRACT FROM AUTHOR]

Combinatorial designs are closely related to linear codes. Recently, some near MDS codes were employed to construct $t$ -designs by Ding and Tang, which settles the question as to whether there exists an infinite family of near MDS codes holding an infinite family of $t$ -designs for $t \geq 2$. This paper is devoted to the construction of infinite families of 3-designs and 2-designs from special equations over finite fields. First, we present an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 3-designs. We then provide an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 2-designs for any field ${\mathrm{ GF}}(q)$. In particular, some of these almost MDS codes are near MDS. Second, we present an infinite family of near MDS codes over ${\mathrm{ GF}}(2^{m})$ holding an infinite family of 3-designs by considering the number of roots of a special linearized polynomial. Compared to previous constructions of 3-designs or 2-designs from linear codes, the parameters of some of our designs are new and flexible. [ABSTRACT FROM AUTHOR]

In this paper, we present two new families of APN functions. The first family is in bivariate form $\big (x^{3}+xy^{2}+ y^{3}+xy, x^{5}+x^{4}y+y^{5}+xy+x^{2}y^{2} \big)\,\,\vphantom {_{\int _{\int }}}$ over ${\mathbb F}_{2^{m}}^{2}$. It is obtained by adding certain terms of the form $\sum _{i}(a_{i}x^{2^{i}}y^{2^{i}},b_{i}x^{2^{i}}y^{2^{i}})$ to a family of APN functions recently proposed by Gölo&gcaron;lu. The $\vphantom {_{\int _{\int }}}$ second family has the form $L(z)^{2^{m}+1}+vz^{2^{m}+1}$ over ${\mathbb F}_{{2^{3m}}}$ , which generalizes a family of APN functions by Bracken et al. from 2011. By calculating the $\Gamma $ -rank of the constructed APN functions over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , we demonstrate that the two families are CCZ-inequivalent to all known families. In addition, the two new families cover two known sporadic APN instances over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , which were found by Edel and Pott in 2009 and by Beierle and Leander in 2021, respectively. [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]

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]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

This paper presents the first systematic study of the zero-error capacity regions of noisy networks. First, we consider two simple such networks, each consisting of a stationary memoryless multiple access channel with two binary inputs and one discrete output. There are two users in each network. Each of the two users transmits a message through the network, and the sink(s) of the network can decode both messages with zero error. A graph is used to represent the distinguishability of the inputs of the channel, and a graph set is used to represent the distinguishability of the inputs of the network. We show that for two networks represented by the same graph set, their zero-error capacity regions are the same. We list all the possible graph sets for the two networks and determine the zero-error capacity regions for some of these graph sets. Based on this result, we explore a relation between graph theory and set theory, and then redefine the cancellative pair of families of subsets. We further extend the problem formulation to a general network called the parallel network, which may consist of more than one channel with multiple inputs and multiple outputs. [ABSTRACT FROM AUTHOR]

The Euclidean hull of a linear code $C$ is the intersection of $C$ with its Euclidean dual $C^\perp $. The hull with low dimensions gets much interest due to its crucial role in determining the complexity of algorithms for computing the automorphism group of a linear code and for checking permutation equivalence of two linear codes. The Euclidean hull of a linear code has been applied to the so-called entanglement-assisted quantum error-correcting codes (EAQECCs) via classical error-correcting codes. In this paper, we firstly consider linear codes with one-dimensional Euclidean hull from algebraic geometry codes, and then present a general method to construct linear codes with arbitrary dimensional Euclidean hull. Some new EAQECCs are presented. [ABSTRACT FROM AUTHOR]

Compared with avid research activities of deep convolutional neural networks (DCNNs) in practice, the study of theoretical behaviors of DCNNs lags heavily behind. In particular, the universal consistency of DCNNs remains open. In this paper, we prove that implementing empirical risk minimization on DCNNs with expansive convolution (with zero-padding) is strongly universally consistent. Motivated by the universal consistency, we conduct a series of experiments to show that without any fully connected layers, DCNNs with expansive convolution perform not worse than the widely used deep neural networks with hybrid structure containing contracting (without zero-padding) convolutional layers and several fully connected layers. [ABSTRACT FROM AUTHOR]

Sum-rank metric codes have recently attracted the attention of many researchers, due to their relevance in several applications. Mathematically, the sum-rank metric is a natural generalization of both the Hamming metric and the rank metric. In this paper, we provide an Anticode Bound for the sum-rank metric, which extends the corresponding Hamming and rank-metric Anticode bounds. We classify then optimal anticodes, i.e., codes attaining the sum-rank metric Anticode Bound. We use these optimal anticodes to define generalized sum-rank weights and we study their main properties. In particular, we prove that the generalized weights of an MSRD code are determined by its parameters. As an application, in the Appendix we explain how generalized weights measure information leakage in multishot network coding. [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]

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]

This paper studies a general framework for high-order tensor SVD. We propose a new computationally efficient algorithm, tensor-train orthogonal iteration (TTOI), that aims to estimate the low tensor-train rank structure from the noisy high-order tensor observation. The proposed TTOI consists of initialization via TT-SVD [Oseledets (2011)] and new iterative backward/forward updates. We develop the general upper bound on estimation error for TTOI with the support of several new representation lemmas on tensor matricizations. By developing a matching information-theoretic lower bound, we also prove that TTOI achieves the minimax optimality under the spiked tensor model. The merits of the proposed TTOI are illustrated through applications to estimation and dimension reduction of high-order Markov processes, numerical studies, and a real data example on New York City taxi travel records. The software of the proposed algorithm is available online (https://github.com/Lili-Zheng-stat/TTOI). [ABSTRACT FROM AUTHOR]

We study spatially coupled LDPC codes that allow access to sub-blocks much smaller than the full code block. Sub-block access is realized by a semi-global decoder that decodes a chosen target sub-block by only accessing the target, plus a prescribed number of helper sub-blocks adjacent in the code chain. This paper develops a theoretical methodology for analyzing the semi-global decoding performance of spatially coupled LDPC codes constructed from protographs. The main result shows that semi-global decoding thresholds can be derived from certain thresholds we define for the single-sub-block graph. These characterizing thresholds are also used for deriving lower bounds on the decoder’s performance over channels with variability across sub-blocks, which are motivated by applications in data storage. [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 this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an $n$ -qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by using $O(n^{2})$ queries to it. For decades, it has been unknown how to handle circuits beyond the Clifford group since the stabilizer formalism cannot be applied in this case. Herein, we study quantum circuits of $T$ -depth one on the computational basis. We show that the output state of a $T$ -depth one circuit can be represented by a stabilizer pseudomixture with a specific algebraic structure. Using Pauli and Bell measurements on copies of the output states, we can generate a hypothesis circuit that is equivalent to the unknown target circuit on computational basis states as input. If the number of $T$ gates of the target is of the order $O({\log n})$ , our algorithm requires $O(n^{2})$ queries to it and produces its equivalent circuit representation on the computational basis in time $O(n^{3})$. Using further additional $O(4^{3n})$ classical computations, we can derive an exact description of the target for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism. [ABSTRACT FROM AUTHOR]

This paper investigates the capacity of general multiple-input single-output (MISO) optical intensity channels (OICs) under per-antenna peak- and average-intensity constraints. We first consider the MISO equal-cost constrained OIC (EC-OIC), where, apart from the peak-intensity constraint, average intensities of inputs are equal to arbitrarily preassigned constants. The second model of our interest is the MISO bounded-cost constrained OIC (BC-OIC), where, as compared with the EC-OIC, average intensities of inputs are no larger than arbitrarily preassigned constants. By leveraging tools from quantile functions, stop-loss transform and convex ordering of nonnegative random variables, we prove two decomposition theorems for bounded and nonnegative random variables, based on which we equivalently transform both the EC-OIC and the BC-OIC into respective single-input single-output channels under a peak-intensity and several stop-loss mean constraints. Capacity lower and upper bounds for both channels are established, based on which the asymptotic capacity at high and low signal-to-noise-ratio are determined. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of signal detection in Gaussian noise in a distributed setting where the local machines in the star topology can communicate a single bit of information. We derive a lower bound on the Euclidian norm that the signal needs to have in order to be detectable. Moreover, we exhibit optimal distributed testing strategies that attain the lower bound. [ABSTRACT FROM AUTHOR]

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate- $1/\omega $ and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose the distance-spectrum optimal (DSO) CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to 1 at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting 64 information bits with a rate-1/2 convolutional encoder. For a target error probability $10^{-4}$ , simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within 0.4 dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values. [ABSTRACT FROM AUTHOR]

Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a real-time status update system in which an energy harvesting (EH)-powered transmitter node observes some physical process, and sends its sensed measurements in the form of status updates to a destination node. The status update and harvested energy packets are assumed to arrive at the transmitter according to independent Poisson processes, and the service time of each status update is assumed to be exponentially distributed. We quantify the freshness of status updates when they reach the destination using the concept of Age of Information (AoI). Unlike most of the existing analyses of AoI focusing on the evaluation of its average value when the transmitter is not subject to energy constraints, our analysis is focused on understanding the distributional properties of AoI through the characterization of its moment generating function (MGF). In particular, we use the stochastic hybrid systems (SHS) framework to derive closed-form expressions of the MGF of AoI under several queueing disciplines at the transmitter, including non-preemptive and preemptive in service/waiting strategies. Using these MGF results, we further obtain closed-form expressions for the first and second moments of AoI in each queueing discipline. We demonstrate the generality of this analysis by recovering several existing results for the corresponding system with no energy constraints as special cases of the new results. Our numerical results verify the analytical findings, and demonstrate the necessity of incorporating the higher moments of AoI in the implementation/optimization of real-time status update systems rather than just relying on its average value. [ABSTRACT FROM AUTHOR]

When the users in a MIMO broadcast channel experience different spatial transmit correlation matrices, a class of gains is produced that is denoted transmit correlation diversity. This idea was conceived for channels in which transmit correlation matrices have mutually exclusive eigenspaces, allowing non-interfering training and transmission. This paper broadens the scope of transmit correlation diversity to the case of partially and fully overlapping eigenspaces and introduces techniques to harvest these generalized gains. For the two-user MIMO broadcast channel, we derive achievable degrees of freedom (DoF) and achievable rate regions with/without channel state information at the receiver (CSIR). When CSIR is available, the proposed achievable DoF region is tight in some configurations of the number of receive antennas and the channel correlation ranks. We then extend the DoF results to the $K$ -user case by analyzing the interference graph that characterizes the overlapping structure of the eigenspaces. Our achievability results employ a combination of product superposition in the common part of the eigenspaces, and pre-beamforming (rate splitting) to create multiple data streams in non-overlapping parts of the eigenspaces. Massive MIMO is a natural example in which spatially correlated link gains are likely to occur. We study the achievable downlink sum rate for a frequency-division duplex massive MIMO system under transmit correlation diversity. [ABSTRACT FROM AUTHOR]

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works. [ABSTRACT FROM AUTHOR]

Deep neural networks (DNNs) achieve impressive results for complicated tasks like object detection on images and speech recognition. Motivated by this practical success, there is now a strong interest in showing good theoretical properties of DNNs. To describe for which tasks DNNs perform well and when they fail, it is a key challenge to understand their performance. The aim of this paper is to contribute to the current statistical theory of DNNs. We apply DNNs on high dimensional data and we show that the least squares regression estimates using DNNs are able to achieve dimensionality reduction in case that the regression function has locally low dimensionality. Consequently, the rate of convergence of the estimate does not depend on its input dimension $d$ , but on its local dimension $d^{*}$ and the DNNs are able to circumvent the curse of dimensionality in case that $d^{*}$ is much smaller than $d$. In our simulation study we provide numerical experiments to support our theoretical result and we compare our estimate with other conventional nonparametric regression estimates. The performance of our estimates is also validated in experiments with real data. [ABSTRACT FROM AUTHOR]

This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice, named $L_{3\cdot 24}$ , is constructed as a simple application of the single parity check on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the $k$ -ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. [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]

Sequences and their correlation properties have been extensively studied due to their broad applications. In this paper, we develop a connection between sequences and well-studied combinatorial objects, circular Florentine arrays. This connection allows us to derive two types of sequences with good correlation properties. The first type consists of sequences having optimal correlation with respect to the Sarwate bound. Our constructions are based on perfect polyphase sequences. The number of perfect sequences with optimal correlation depends on the existence of circular Florentine arrays, which improves the previous known results. The second type is about multiple ZCZ sequence sets with low inter-set cross-correlation. Each generated ZCZ sequence set is optimal with respect to the Tang-Fan-Matsufuji bound, and each sequence in each set is perfect. In addition, any two sequences from distinct ZCZ sequence sets possess optimal inter-set cross-correlation with respect to the Sarwate bound. Compared with the previous results, the number of ZCZ sequence sets with optimal inter-set cross-correlation property is improved, because of the existence of circular Florentine arrays. [ABSTRACT FROM AUTHOR]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [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]

Recently, Liu and Zhang studied the rather challenging problem of time series forecasting from the perspective of compressed sensing. They proposed a no-learning method, named Convolution Nuclear Norm Minimization (CNNM), and proved that CNNM can exactly recover the future part of a series from its observed part, provided that the series is convolutionally low-rank. While impressive, the convolutional low-rankness condition may not be satisfied whenever the series is far from being seasonal, and is in fact brittle to the presence of trends and dynamics. This paper tries to approach the issues by integrating a learnable, orthonormal transformation into CNNM, with the purpose for converting the series of involute structures into regular signals of convolutionally low-rank. We prove that the resultant model, termed Learning-Based CNNM (LbCNNM), strictly succeeds in identifying the future part of a series, as long as the transform of the series is convolutionally low-rank. To learn proper transformations that may meet the required success conditions, we devise an interpretable method based on Principal Component Pursuit (PCP). Equipped with this learning method and some elaborate data argumentation skills, LbCNNM not only can handle well the major components of time series (including trends, seasonality and dynamics), but also can make use of the forecasts provided by some other forecasting methods; this means LbCNNM can be used as a general tool for model combination. Extensive experiments on 100,452 real-world time series from Time Series Data Library (TSDL) and M4 Competition (M4) demonstrate the superior performance of LbCNNM. [ABSTRACT FROM AUTHOR]

Quantum LDPC codes are a promising direction for low overhead quantum computing. In this paper, we propose a generalization of the Union-Find decoder as a decoder for quantum LDPC codes. We prove that this decoder corrects all errors with weight up to $An^\alpha $ for some $A, \alpha > 0$ , where $n$ is the code length, for different classes of quantum LDPC codes such as toric codes and hyperbolic codes in any dimension $D \geq 3$ and quantum expander codes. To prove this result, we introduce a notion of covering radius which measures the spread of an error from its syndrome. We believe this notion could find application beyond the decoding problem. We also perform numerical simulations, which show that our Union-Find decoder outperforms the belief propagation decoder in the low error rate regime in the case of a quantum LDPC code with length 3600. [ABSTRACT FROM AUTHOR]

In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield codes in terms of generator matrices and defining sets. Second, we construct quaternary linear codes via simplicial complexes and determine the weight distributions of these codes. Third, the weight distributions of the binary subfield codes of these quaternary codes are also computed by employing the general characterization. Furthermore, we present two infinite families of optimal linear codes with respect to the Griesmer Bound, and a class of binary almost optimal codes with respect to the Sphere Packing Bound. We also need to emphasize that we obtain at least 9 new quaternary linear codes. [ABSTRACT FROM AUTHOR]

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta }$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta $ of tests an individual can be placed in, or the maximum number $\Gamma $ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta $ -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma $ -sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta (1)$ , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms. [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]