Search

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write $n$ incoming packets and read $k$ outgoing packets while using $m$ memory banks, each able to write and read one packet per time unit. Each set of $n$ packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of $k$ packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case $n=k$ . [ABSTRACT FROM AUTHOR]

The main result of this paper is that an orthogonal access scheme, such as time division multiple access achieves the all-unicast degrees of freedom (DoF) region of the topological interference management problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem. [ABSTRACT FROM PUBLISHER]

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants \delta tk (00,\,\,\delta tk<({t}/({4-t}))+\epsilon cannot guarantee the exact recovery of some k -sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang’s work, a complete characterization for sharp RIP constants \delta _{tk} for all t > 0$ is obtained to guarantee the exact recovery of all k$ -sparse signals and matrices with rank at most k$ by -norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order $tk$ , which is the target of our main results, can be perfectly applied to them. [ABSTRACT FROM PUBLISHER]

In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most \mathcal O(\log ^2(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case \mathcal O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by \mathcal O(\log ^2(n)) broadcast transmissions. We extend our algorithm to the t -requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most \mathcal O(t\log (n)+\log ^2(n)) broadcast transmissions. We construct lower bound instances that require at least \Omega (\log (n)) transmissions for linear pliable index coding and at least $\Omega (t+\log (n))$ transmissions for the t$ -requests case, indicating that both our upper and lower bounds are polynomials of \log (n)$ and differ within a factor of . We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely $\Theta (\log (n))$ , as compared with the $\Theta (n/\log (n))$ for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions. [ABSTRACT FROM AUTHOR]

This paper presents a study of perturbations of symmetric Boolean functions. In particular, it establishes a connection between exponential sums of these perturbations and Diophantine equations of the form \sum l=0^{n} \binom {n}{l} xl=0 , where xj belongs to some fixed bounded subset $\Gamma $ of \mathbb {Z} . The concepts of trivially balanced symmetric Boolean function and sporadic balanced Boolean function are extended to this type of perturbations. An observation made by Canteaut and Videau for symmetric Boolean functions of fixed degree is extended. To be specific, it is proved that, excluding the trivial cases, balanced perturbations of fixed degree do not exist when the number of variables grows. Some sporadic balanced perturbations are presented. Finally, a beautiful but unexpected identity between exponential sums for perturbations of two different symmetric Boolean functions is also included in this work. [ABSTRACT FROM AUTHOR]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

The Johnson-type upper bound on the maximum size of a code of length n , distance d=2w-1 , and constant composition \overline w is \lfloor \dfrac \vphantom R^.nw1\rfloor , where w is the total weight and w_{1} is the largest component of {\overline {w}} . Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let Nccc({\overline {w}}) be the smallest such length. The determination of Nccc({\overline {w}}) is trivial for binary codes. This paper provides a lower bound on Nccc({\overline {w}}) , which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by the refining method, we determine the values of Nccc({\overline {w}}) , for all $q$ -ary constant-composition codes, provided that 3w_{1}\geq w with finite possible exceptions. [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a \delta s -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the \delta s -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code. [ABSTRACT FROM AUTHOR]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k -radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k -radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k -radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k -radius sequences for certain values of n , by establishing the existence of k -additive sequences. In particular, we show that for any fixed k , where fk (n) denotes the shortest length of an n -ary $k$ -radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rzążewski. [ABSTRACT FROM AUTHOR]

Let p be a prime, n=2m and d=3p^m-2 with m\geq 2 , and \gcd (d,p^n-1)=1 . In this paper, the correlation distribution between a p -ary m -sequence of period p^n-1 and its d -decimation sequence is investigated in a unified approach. Some results for the binary case are extended to the general case. It is shown that the problem of determining the correlation distribution for d can be reduced to that of solving two combinatorial problems related to the unit circle of the finite field \mathbb {F}_{p^{n}} . For an arbitrary odd prime p , it seems difficult to solve these two problems. However, for p=3 , by studying the weight distribution of the ternary Zetterberg code and counting the numbers of solutions of some equations over \mathbb {F}_{3^{n}} , the two problems are solved, and thus, the corresponding correlation distribution for d$ is completely determined. It is noteworthy that this is the first time that the correlation distribution for a non-binary Niho decimation has been determined since 1976. [ABSTRACT FROM PUBLISHER]

In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper, we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,\epsilon )$ -disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$ -set of defective subjects out of a population of size $N$ with false positive probability of an item at most $\epsilon $ . We establish a new connection between $(t,\epsilon )$ -disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs. [ABSTRACT FROM PUBLISHER]

In the classical non-adaptive group testing setup, pools of items are tested together, and the main goal of a recovery algorithm is to identify the complete defective set given the outcomes of different group tests. In contrast, the main goal of a non-defective subset recovery algorithm is to identify a subset of non-defective items given the test outcomes. In this paper, we present a suite of computationally efficient and analytically tractable non-defective subset recovery algorithms. By analyzing the probability of error of the algorithms, we obtain bounds on the number of tests required for non-defective subset recovery with arbitrarily small probability of error. Our analysis accounts for the impact of both the additive noise (false positives) and dilution noise (false negatives). By comparing with information theoretic lower bounds, we show that the upper bounds on the number of tests are orderwise tight up to a \log ^2K factor, where $K$ is the number of defective items. We also provide simulation results that compare the relative performance of the different algorithms and reveal insights into their practical utility. The proposed algorithms significantly outperform the straightforward approaches of testing items one-by-one, and of first identifying the defective set and then choosing the non-defective items from the complement set, in terms of the number of measurements required to ensure a given success rate. [ABSTRACT FROM PUBLISHER]

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length N$ over an alphabet of size q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when q$ is small compared with w$ , say cq\leq w$ for some constant c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary w . [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the index coding problem in the presence of an eavesdropper. Messages are to be sent from one transmitter to a number of legitimate receivers who have side information about the messages, and share a set of secret keys with the transmitter. To do this, the transmitter communicates to the legitimate receivers the public code $C$ , which is also heard by the eavesdropper. We assume perfect secrecy, meaning that the eavesdropper should not be able to retrieve any information about the message set from the public communication. We study the minimum key lengths for zero-error and perfectly secure index coding problem. On one hand, this problem is a generalization of the index coding problem (and thus a difficult one). On the other hand, it is a generalization of the Shannon’s cipher system. We show that a generalization of Shannon’s one-time pad strategy is optimal up to a multiplicative constant, meaning that it obtains the entire boundary of the cone formed by looking at the secure rate region from the origin. This shows the optimality of the generalized one-time pad for minimizing the consumption of shared secret keys per message bits, when public communication is free (the transmitter is not charged for the rate of the public communication). Finally, we consider relaxation of the perfect secrecy and zero-error constraints to weak secrecy and asymptotically vanishing probability of error, and provide a secure version of the result, obtained by Langberg and Effros, on the equivalence of zero-error and $\epsilon $ -error regions in the conventional index coding problem. [ABSTRACT FROM PUBLISHER]

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in the literature, called, respectively, fix-free code and non-overlapping code. In this paper we present constructive algorithms for such codes and some numerical results about their cardinality. [ABSTRACT FROM PUBLISHER]

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over \mathop \mathrm GR\nolimits (2^a,m) of length 2^s have been characterized: the ring \mathcal R2(a,m,-1)= {\mathrm{ GR}}(2^{a},m)[x]/\langle x^{2^{s}}+1\rangle is a chain ring. Furthermore, these results have been generalized to \lambda -constacyclic codes for any unit \lambda of the form 4z-1 , . In this paper, we study more general cases and investigate all cases, where {\mathcal{ R}}_{p}(a,m,\gamma) = {\mathrm{ GR}}(p^{a},m)[x]/\langle x^{p^{s}}-\gamma \rangle is a chain ring. In particular, the necessary and sufficient conditions for the ring {\mathcal{ R}}_{p}(a,m,\gamma) to be a chain ring are obtained. In addition, by using this structure we investigate all \gamma -constacyclic codes over \mathop {\mathrm {GR}}\nolimits (p^{a},m) when {\mathcal{ R}}_{p}(a,m,\gamma)$ is a chain ring. The necessary and sufficient conditions for the existence of self-orthogonal and self-dual \gamma$ -constacyclic codes are also provided. Among others, for any prime p$ , the structure of is used to establish the Hamming and homogeneous distances of $\gamma$ -constacyclic codes. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a $k$ th-order tensor of multilinear rank r$ and dimension d \times \cdots \times d$ can be recovered perfectly from as few as uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: they not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors. Although our focus is primarily on the theoretical guarantees for nuclear norm minimization, such insights may prove useful for understanding performance of other related methods and developing improved practical algorithms. [ABSTRACT FROM PUBLISHER]

Pairs of binary sequences formed using linear combinations of multiplicative characters of finite fields are exhibited that, when compared with a random sequence pairs, simultaneously achieve significantly lower mean square autocorrelation values (for each sequence in the pair) and significantly lower mean square crosscorrelation values. If we define crosscorrelation merit factor analogously to the usual merit factor for autocorrelation, and if we define demerit factor as the reciprocal of merit factor, then randomly selected binary sequence pairs are known to have an average crosscorrelation demerit factor of 1. Our constructions provide sequence pairs with a crosscorrelation demerit factor significantly less than 1, and at the same time, the autocorrelation demerit factors of the individual sequences can also be made significantly less than 1 (which also indicates better than average performance). The sequence pairs studied here provide combinations of autocorrelation and crosscorrelation performance that are not achievable using sequences formed from single characters, such as maximal linear recursive sequences (m-sequences) and Legendre sequences. In this paper, exact asymptotic formulae are proved for the autocorrelation and crosscorrelation merit factors of sequence pairs formed using linear combinations of multiplicative characters. Data is presented that shows that the asymptotic behavior is closely approximated by sequences of modest length. [ABSTRACT FROM PUBLISHER]

Caching is a promising solution to satisfy the ever-increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into F packets, which usually increases exponentially with the number of users K . Thus, designing caching schemes that decrease the order of F is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least F . Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (identical cache size is assumed at all users) and the number of files N ( q is an integer, such that q\geq 2 ). The new construction can decrease the required F of Ali-Niesen scheme to O(e^{K\cdot ({M}/{N})\ln \!\,({N}/\!{M})}) or O(e^{K\cdot (1-({M}/\!{N}))\ln \!\,(N/(N-M))})$ , respectively, while the coding gain loss is only 1. [ABSTRACT FROM AUTHOR]

It is well known that cooperation between users in a communication network can lead to significant performance gains. A common assumption in past works is that all the users are aware of the resources available for cooperation, and know exactly to what extent these resources can be used. Unfortunately, in many modern communication networks, the availability of cooperation links cannot be guaranteed a priori, due to the dynamic nature of the network. In this paper, a family of models is suggested where the cooperation links may or may not be present. Coding schemes are devised that exploit the cooperation links if they are present, and can still operate (although at reduced rates) if cooperation is not possible. [ABSTRACT FROM AUTHOR]

The approximation of stable linear time-invariant (LTI) systems is studied for the Paley–Wiener space \mathcal PW\pi ^{1} of bandlimited functions with absolutely integrable Fourier transform. For pointwise sampling, it is known that there exist stable LTI systems and functions such that the approximation process diverges, regardless of the oversampling factor. Recently, it was shown that the divergence can be overcome by using more general measurement functionals that are based on a complete orthonormal system. However, this approach requires the approximation process to have an increased bandwidth. In this paper, a two channel approximation process is presented that is uniformly convergent for all stable LTI systems and all functions in \mathcal PW\pi ^{1} . An advantage of the two channel approach compared with the one channel approach is the reduction of the approximation bandwidth, which can be exactly the same as the input function bandwidth. [ABSTRACT FROM AUTHOR]

In the mid 1960s, Rothaus proposed the so-called “most general form” of constructing new bent functions by using three (initial) bent functions whose sum is again bent. In this paper, we utilize a special case of Rothaus construction when two of these three bent functions differ by a suitably chosen characteristic function of an $n/2$ -dimensional subspace. This simplification allows us to treat the induced bent conditions more easily, also implying the possibility to specify the initial functions in the partial spread class and most notably to identify several instances of the so-called non-normal bent functions. Affine inequivalent bent functions within this class are then identified using a suitable selection of initial bent functions within the partial spread class (stemming from the complete Desarguesian spread). It is also shown that when the initial bent functions belong to the class \mathcal {D} , then, under certain conditions, the constructed functions provably do not belong to the completed Maiorana–McFarland class. We conjecture that our method potentially generates an infinite class of non-normal bent functions (all tested ten-variable functions are non-normal but unfortunately they are weakly normal) though there are no efficient computational tools for confirming this. [ABSTRACT FROM AUTHOR]

Write-once memory (WOM) is a storage device consisting of $q$ -ary cells that can only increase their value. A WOM code is a coding scheme that allows writing multiple times to the memory without decreasing the levels of the cells. In the conventional model, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding. However, there are three more models in this setup, which depend on whether the encoder and the decoder are informed or uninformed with the previous state of the memory. These four models were first introduced by Wolf et al., where they extensively studied the WOM capacity in these models for the binary case. In the non-binary setup, only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Vinck. In this paper, we first present constructions of WOM codes in the models where the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We then study the capacity regions and maximum sum-rates of non-binary WOM codes for all four models. We extend the results by Wolf et al. and show that the capacity regions for the models in which the encoder is informed and the decoder is informed or uninformed in both the $\epsilon $ -error and the zero-error cases are all identical. We also find the $\epsilon $ -error capacity region; in this case, the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well. [ABSTRACT FROM AUTHOR]

A primary objective of a distributed storage system is to reliably store huge amounts of source data for long periods of time using a large number of high storage capacity nodes. Storage nodes are prone to permanent failures, where such node failures cause all stored data to be permanently lost, and failed nodes are replaced with nodes that initially store no data. To maintain recoverability of the source data as storage nodes fail and are replaced, a total amount of storage capacity that is larger than the source data size is allocated to store the source data, and a repairer continually reads data from and writes data to the storage nodes as they fail and are replaced. We prove information-theoretic lower bounds on the rate at which a repairer reads data from the storage system as a function of the rate at which nodes fail and the amount by which the allocated storage capacity exceeds the source data size. These lower bounds hold for any repairer, i.e., any repairer that does not read data at or above the lower bound rate will provably not maintain recoverability of the source data. The bounds are provably tight asymptotically as the number of storage nodes grows and the allocated storage capacity approaches the source data size. [ABSTRACT FROM AUTHOR]

Caching is often used in content delivery networks as a mechanism for reducing network traffic. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server were considered. Prior results in this area demonstrate that carefully designing the placement of content in the caches and designing appropriate coded delivery signals from the server allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching upper and lower bounds on the transmission rate have not yet been obtained. In this paper, we derive tighter lower bounds on the coded caching rate than were known previously. We demonstrate that this problem can equivalently be posed as a combinatorial problem of optimally labeling the leaves of a directed tree. Our proposed labeling algorithm allows for significantly improved lower bounds on the coded caching rate. Furthermore, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound for general values of the problem parameters. This allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound. [ABSTRACT FROM PUBLISHER]

Our first goal in this paper is to investigate stationarization and asymptotic decorrelation for fractional Brownian motion (fBm) using wavelet packet transform. The wavelet packets are generated by the N^\mathrm th -order Daubechies scaling function and wavelet. To decorrelate the wavelet packet coefficients asymptotically, we take two strategies: fix $N$ and let absolute scale difference or absolute difference between time shifts get large; and fix scale level and time shift and let $N$ get large. Our second goal is to present the asymptotic properties of the entropy-like cost functional and denoising cost functional and their impact on the selection of best wavelet packet bases when used for fBm plus or not plus independent Gaussian white noise. [ABSTRACT FROM PUBLISHER]

Suppose Y^n is obtained by observing a uniform Bernoulli random vector X^n through a binary symmetric channel. Courtade and Kumar asked how large the mutual information between Y^n and a Boolean function \mathsf b(X^n) could be, and conjectured that the maximum is attained by a dictator function. An equivalent formulation of this conjecture is that dictator minimizes the prediction cost in a sequential prediction of Y^n under logarithmic loss, given \mathsf b(X^n) . In this paper, we study the question of minimizing the sequential prediction cost under a different (proper) loss function—the quadratic loss. In the noiseless case, we show that majority asymptotically minimizes this prediction cost among all Boolean functions. We further show that for weak noise, majority is better than a dictator, and that for a strong noise dictator outperforms majority. We conjecture that for quadratic loss, there is no single sequence of Boolean functions that is simultaneously (asymptotically) optimal at all noise levels. [ABSTRACT FROM PUBLISHER]

We consider the canonical shared link caching network formed by a source node, hosting a library of $m$ information messages (files), connected via a noiseless multicast link to $n$ user nodes, each equipped with a cache of size $M$ files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting. [ABSTRACT FROM AUTHOR]

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

A normal rational curve of the (k-1) -dimensional projective space over {\mathbb F}_{q} is an arc of size q+1$ , since any k$ points of the curve span the whole space. In this paper, we will prove that if q$ is odd, then a subset of size 3k-6$ of a normal rational curve cannot be extended to an arc of size q+2$ . In fact, we prove something slightly stronger. Suppose that q$ is odd and E$ is a (2k-3)$ -subset of an arc G$ of size 3k-6$ . If G$ projects to a subset of a conic from every (k-3)$ -subset of E of odd characteristic, which can be extended to a Reed–Solomon code of length $q+1$ , cannot be extended to a linear maximum distance separable code of length $q+2$ . [ABSTRACT FROM AUTHOR]

We consider a graphical approach to index coding. As cycles have been shown to provide coding gain, cycles and cliques (a specific type of overlapping cycles) have been exploited in an existing literature. In this paper, we define a more general form of overlapping cycles, called the interlinked-cycle ( \mathsf IC ) structure, that generalizes cycles and cliques. We propose a scheme, called the interlinked-cycle-cover ( \mathsf ICC ) scheme, that leverages \mathsf IC structures in digraphs to construct scalar linear index codes. We characterize a class of infinitely many digraphs where our proposed scheme is optimal over all linear and non-linear index codes. Consequently, for this class of digraphs, we indirectly prove that scalar linear index codes are optimal. Furthermore, we show that the \mathsf ICC scheme can outperform all the existing graph-based schemes (including partial-clique-cover and fractional-local-chromatic number schemes), and a random-coding scheme (namely, composite coding) for certain graphs. [ABSTRACT FROM AUTHOR]

A linear complementary dual (LCD) code is a linear code with complimentary dual. LCD codes have been extensively studied in literature. On the other hand, maximum distance separable (MDS) codes are an important class of linear codes that have found wide applications in both theory and practice. However, little is known about MDS codes with complimentary duals. The main purpose of this paper is to construct several classes of MDS codes with complimentary duals, i.e., LCD MDS codes, through generalized Reed-Solomon codes. [ABSTRACT FROM PUBLISHER]

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols. [ABSTRACT FROM PUBLISHER]

In this paper, we address the problem of the universal coding of natural numbers. A new numeration system is introduced, which is based on variable- $r$ meta-Fibonacci sequences and it is a generalization of the Zeckendorf numeration system. This new numeration system is used to construct binary, prefix-free, uniquely decodable universal codes called meta-Fibonacci codes. The main advantage of these codes is that they are parametrized by a sequence of numbers, the sequence o. By controlling the growth of the values of this sequence, we can control the length of the code word. This means that we can provide a general framework for building efficient universal coders for natural numbers. Such framework is applied to the upper bounds of the code word length defined by Leung-Yan-Cheong and Cover (1978), Levenshtein (1968), and Ahlswede (1997). There is no other code meeting these bounds. In each case, we build meta-Fibonacci codes and demonstrate that the upper bound of their code word length is satisfied up to an additive constant, thereby solving these open problems. The framework may be applied to other upper bounds that satisfy Kraft inequality. [ABSTRACT FROM PUBLISHER]

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and \gcd (n, k)=1 , it is known that the Coulter–Matthews bent function f(x)=Tr\left(ax^\frac 3^k+12\right) is weakly regular bent over \mathbb F3^{n} , where a\in \mathbb F3^{n}^{*} , and Tr(\cdot ):\mathbb F3^{n}\rightarrow \mathbb F3 is the trace function. In this paper, we investigate the dual function of $f(x)$ , aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n=3t+1$ and k=2t+1$ with t\geq 2n=3t+2$ and k=2t+1$ with t\geq 2f(x)$ is regular bent. [ABSTRACT FROM PUBLISHER]

Broadcasting $K$ independent messages to multiple users where each user demands all the messages and already has a subset of the messages as side information is studied. Recently, Natarajan et al. proposed a novel broadcasting strategy called lattice index coding, which adopts lattices constructed over some principal ideal domains (PID) for transmission. Using the structure of lattices over PID, they showed that this scheme provides uniform side information gain for any side information configuration, a desired property which essentially guarantees a fair signal-to-noise ratio gain when normalized by the amount of information contained in side information. In this paper, we generalize this strategy to a general ring of algebraic integers, which may not be a PID. Upper and lower bounds on the side information gains for the proposed scheme constructed over some interesting classes of number fields are provided and are shown to coincide asymptotically in message rate. This generalization substantially enlarges the design space and partially includes the scheme by Natarajan et al. as a special case. Perhaps more importantly, in addition to side information gains, the proposed lattice index codes benefit from diversity gains inherent in constellations carved from number fields when used over Rayleigh fading channel. Some interesting examples are provided for which the proposed scheme allows the messages to be from the same field. [ABSTRACT FROM PUBLISHER]

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of q -ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where q is even. This paper focuses on the case where q is odd. We construct a few classes of new MDS self-dual codes through generalized Reed–Solomon codes. More precisely, we show that for any given even length n , we have a q and q is sufficiently large (say q\ge 4^{n}\times n^{2}) . Furthermore, we prove that there exists a q -ary MDS self-dual code of length n if q=r^{2} and n$ satisfies one of the three conditions: 1) n\le r$ and n$ is even; 2) q$ is odd and n-1$ is an odd divisor of and $n=2tr$ for any $t\le (r-1)/2$ . [ABSTRACT FROM PUBLISHER]

In this paper, we introduce the so-called hierarchical interaction models, where we assume that the computation of the value of a function m: \mathbb R^d\rightarrow \mathbb R is done in several layers, where in each layer a function of at most d^* inputs computed by the previous layer is evaluated. We investigate two different regression estimates based on polynomial splines and on neural networks, and show that if the regression function satisfies a hierarchical interaction model and all occurring functions in the model are smooth, the rate of convergence of these estimates depends on d^* (and not on $d$ ). Hence, in this case, the estimates can achieve good rate of convergence even for large $d$ , and are in this sense able to circumvent the so-called curse of dimensionality. [ABSTRACT FROM PUBLISHER]

In this paper, we solve the open problems raised in [8] and present some examples to illustrate the obtained results. Moreover, we work out the diophantine problem by Shi and Wang and then give the sufficient conditions for the nonexistence of two-Lee weight projective codes over \mathbb Z4 with type 4^k12^{k2} . [ABSTRACT FROM PUBLISHER]

Given n discrete random variables, its entropy vector is the 2^{n}-1 -dimensional vector obtained from the joint entropies of all non-empty subsets of the random variables. It is well known that there is a close relation between such an entropy vector and a certain group-characterizable vector obtained from a finite group and n of its subgroups; indeed, roughly speaking, knowing the region of all such group-characterizable vectors is equivalent to knowing the region of all entropy vectors. This correspondence may be useful for characterizing the space of entropic vectors and for designing network codes. If one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al. that linear network codes cannot achieve capacity in general network coding problems (since linear network codes come from abelian groups). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. General entropy vectors, however, do not necessarily have this property. It is, therefore, of interest to identify groups that violate the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors, which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2,q) with a prime power q \geq 5 , i.e., the projective group of 2\times 2 nonsingular matrices with entries in \mathbb Fq . We further interpret this family of groups, and their subgroups, using the theory of group actions and identify the subgroups as certain stabilizers. We also extend the construction to more general groups such as PGL(n,q) and $GL(n,q)$ . The families of groups identified here are therefore good candidates for constructing network codes more powerful than linear network codes, and we discuss some considerations for constructing such group network codes. [ABSTRACT FROM PUBLISHER]

In this paper, list decoding of crisscross errors in arrays over finite fields is considered. For this purpose, the so-called cover metric is used, where the cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. A Johnson-like upper bound on the maximum list size in the cover metric is derived, showing that the list of codewords has polynomial size up to a certain radius. Furthermore, a simple list decoding algorithm for a known optimal code construction is presented, which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors. [ABSTRACT FROM PUBLISHER]

In this paper, let n=2k and d=3\cdot 2^{k}-2 with k\geq 3 and \gcd (d,2^n-1)=1 . Based on some analysis of certain equations over finite fields and the number of codewords with Hamming weight five in Zetterberg code, the correlation distribution between a binary m -sequence of period 2^n-1 and its $d$ -decimation sequence is completely determined. This solves a ten-year-old open problem proposed by Dobbertin et al. [ABSTRACT FROM PUBLISHER]

Golay complementary sequences and complementary sets have been proposed to deal with the high peak-to-average power ratio (PAPR) problem in orthogonal frequency division multiplexing (OFDM) system. The existing constructions of complementary sets based on generalized Boolean functions are limited to lengths, which are powers of two. In this paper, we propose novel constructions of binary and nonbinary complementary sets of non-power-of-two length. Regardless of whether or not the length of the complementary set is a power of two, its PAPR is still upper bounded by the size of the complementary set. Therefore, the constructed complementary sets can be applied in practical OFDM systems where the number of used subcarriers is not a power of two. In addition, while the binary Golay complementary pairs exist only for limited lengths, the constructed binary complementary sets of size 4 exist for more lengths with PAPR at most 4. [ABSTRACT FROM PUBLISHER]

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class \mathcal N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF( q ) but not over GF( q' ) with q < q' , based on a subgroup order criterion. In particular: 1) for every k\geq 2 ) but not over GF( 2^{2k+1} ) and 2) for arbitrary distinct primes p and p' , there are infinitely many k and k' ) but not over GF( p'^k' ) with p^k < p'^k' . [ABSTRACT FROM PUBLISHER]

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature. [ABSTRACT FROM PUBLISHER]

Projective Reed–Muller codes were introduced by Lachaud in 1988 and their dimension and minimum distance were determined by Serre and Sørensen in 1991. In coding theory, one is also interested in the higher Hamming weights, to study the code performance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as the next-to-minimal weight) is completely determined. In this paper, we determine all the values of the next-to-minimal weight for the binary projective Reed–Muller codes, which we show to be equal to the next-to-minimal weight of Reed–Muller codes in most, but not all, cases. [ABSTRACT FROM PUBLISHER]

Group-based sparsity models are instrumental in linear and non-linear regression problems. The main premise of these models is the recovery of “interpretable” signals through the identification of their constituent groups, which can also provably translate in substantial savings in the number of measurements for linear models in compressive sensing. In this paper, we establish a combinatorial framework for group-model selection problems and highlight the underlying tractability issues. In particular, we show that the group-model selection problem is equivalent to the well-known NP-hard weighted maximum coverage problem. Leveraging a graph-based understanding of group models, we describe group structures that enable correct model selection in polynomial time via dynamic programming. Furthermore, we show that popular group structures can be explained by linear inequalities involving totally unimodular matrices, which afford other polynomial time algorithms based on relaxations. We also present a generalization of the group model that allows for within group sparsity, which can be used to model hierarchical sparsity. Finally, we study the Pareto frontier between approximation error and sparsity budget of group-sparse approximations for two tractable models, among which the tree sparsity model, and illustrate selection and computation tradeoffs between our framework and the existing convex relaxations. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel “genie chains” approach to obtain information theoretic degrees of freedom (DoF) outer bounds for MIMO wireless interference networks. This new approach creates a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, and then the exposed signal spaces serve as the genie signals for the next receiver in the chain subject to certain linear independence requirements. Our approach essentially converts an information theoretic DoF outer bound problem into a linear algebra problem. Several applications of the genie chains approach are presented. [ABSTRACT FROM AUTHOR]

We study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most N/M file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file F scales to infinity. The asymptotic coding gain obtained is roughly t=KM/N . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets F is a function of the system parameters . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of ({4}/{3})g is at least O(({g}/{K})(N/M)^{g-1})$ . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. [ABSTRACT FROM AUTHOR]