Search

A network of three nodes mutually communicating with each other is studied. This multi-way network is a suitable model for three-user device-to-device communications. The main goal of this paper is to characterize the capacity region of the underlying Gaussian three-way channel (3WC) within a constant gap. To this end, a capacity outer bound is derived using cut-set bounds and genie-aided bounds. For achievability, the 3WC is first transformed into an equivalent star channel. This latter is then decomposed into a set of “successive” sub-channels, leading to a sub-channel allocation problem. Using backward decoding, interference neutralization, and known results on the capacity of the star-channel relying of physical-layer network coding, an achievable rate region for the 3WC is obtained. It is then shown that the achievable rate region is within a constant gap of the developed outer bound, leading to the desired capacity approximation. Interestingly, in contrast to the Gaussian two-way channel (TWC), adaptation is necessary in the 3WC. Furthermore, message splitting is another ingredient of the developed scheme for the 3WC, which is not required in the TWC. The two setups are, however, similar in terms of their sum-capacity pre-log, which is equal to 2. Finally, some interesting networks and their approximate capacities are recovered as special cases of the 3WC, such as the cooperative broadcast channel and multiple access channel. [ABSTRACT FROM PUBLISHER]

Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide roughly the following guarantee: if a codeword c encoding some message x is tampered to c' = f(c) such that c' \neq c , then the tampered message x' contained in c' reveals no information about x . The non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions f . However, in this paper we show “the next best thing”: for any polynomial bound s of size | \mathcal F| \leq 2^s , there is an efficient non-malleable code that protects against all f \in \mathcal F . The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the “common reference string” model. We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x' = f(x)$ , the derived key $y' = h(x')$ does not reveal any information about $y$ . Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of “leakage-resilient storage” of Davì, Dziembowski, and Venturi (SCN ’10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes. [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]

In this paper, we consider optimal q -ary cyclic constant-weight codes of length n , minimum distance d , and weight w codes. We introduce the pure and mixed difference method to present a combinatorial description for a cyclic (n,d,w)_{q} code and then obtain some tight upper bounds on the sizes of optimal cyclic (n,d,w)_{q} codes. Finally, by using Skolem-type sequences, we completely determine the sizes of optimal cyclic (n,d,3)3 codes with minimum distance 1\leq d\leq 6 . [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2\sum i=1^{m}wi-2 or $2mw-2w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely. [ABSTRACT FROM AUTHOR]

This paper offers a characterization of fundamental limits on the classification and reconstruction of high-dimensional signals from low-dimensional features, in the presence of side information. We consider a scenario where a decoder has access both to linear features of the signal of interest and to linear features of the side information signal; while the side information may be in a compressed form, the objective is recovery or classification of the primary signal, not the side information. The signal of interest and the side information are each assumed to have (distinct) latent discrete labels; conditioned on these two labels, the signal of interest and side information are drawn from a multivariate Gaussian distribution that correlates the two. With joint probabilities on the latent labels, the overall signal-(side information) representation is defined by a Gaussian mixture model. By considering bounds to the misclassification probability associated with the recovery of the underlying signal label, and bounds to the reconstruction error associated with the recovery of the signal of interest itself, we then provide sharp sufficient and/or necessary conditions for these quantities to approach zero when the covariance matrices of the Gaussians are nearly low rank. These conditions, which are reminiscent of the well-known Slepian–Wolf and Wyner–Ziv conditions, are the function of the number of linear features extracted from signal of interest, the number of linear features extracted from the side information signal, and the geometry of these signals and their interplay. Moreover, on assuming that the signal of interest and the side information obey such an approximately low-rank model, we derive the expansions of the reconstruction error as a function of the deviation from an exactly low-rank model; such expansions also allow the identification of operational regimes, where the impact of side information on signal reconstruction is most relevant. Our framework, which offers a principled mechanism to integrate side information in high-dimensional data problems, is also tested in the context of imaging applications. In particular, we report state-of-the-art results in compressive hyperspectral imaging applications, where the accompanying side information is a conventional digital photograph. [ABSTRACT FROM PUBLISHER]

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$ , i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$ , dimension $k$ , locality $r$ , availability $t$ , and field size $q$ . Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed–Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code. [ABSTRACT FROM PUBLISHER]

In this paper we extend the notion of locally repairable codes to secret sharing schemes. The main problem that we consider is to find optimal ways to distribute the shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using the contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a passive eavesdropper that can observe some subsets of nodes. We provide a number of results related to such systems, including upper bounds and achievability results on the number of bits that can be securely stored with these constraints. In particular, we provide conditions under which a locally repairable code can be turned into a secret sharing scheme and extend the results of secure repairable storage to cooperative repair and storage on networks. In addition, we consider perfect secret sharing schemes over general access structures under locality constraints and give an example of a perfect secret sharing scheme that can have small locality. Finally, we provide a lower bound on the size of a share compared with the size of the secret that shows how locality affects the sizes of shares in a perfect scheme. [ABSTRACT FROM PUBLISHER]

Combinatorial structures called stopping sets are useful in analyzing the performance of a linear code when coupled with an iterative decoding algorithm over an erasure channel. In this paper, we consider stopping sets of Hermitian codes. [ABSTRACT FROM PUBLISHER]

Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order \mathcal O(n\lg (n)) , where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequency-domain decoding algorithms for (n=2^{m},k) systematic Reed–Solomon (RS) codes over \mathbb {F}_{2^{m}},m\in \mathbb {Z}^{+} , with n-k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is \mathcal {O}(n\lg (n-k)+(n-k)\lg ^{2}(n-k)) , improving upon the best currently available decoding complexity \mathcal {O}(n\lg ^{2}(n)\lg \lg (n)) , and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen’s approach is only for the codes over some specific fields, which can apply Cooley–Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (2^16,2^15) RS code over \mathbb F2^16 . [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]

The restricted isometry property (RIP) is a fundamental property of a matrix, which enables sparse recovery. Informally, an m \times n matrix satisfies RIP of order k for the \ell p norm, if \Ax\p \approx \x\p for every vector x with at most k non-zero coordinates. For every 1 \leq p < \infty , we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this paper, only the cases p = 1 , 1 + 1 / \log n , and 2 were studied. Interestingly, our results show that the case p = 2 for all p\in [1,\infty )\setminus \2\ , as opposed to \widetilde \Theta (k) for $p=2$ . We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss the implications of our results for the stable sparse recovery problem as defined by Candès et al. [ABSTRACT FROM AUTHOR]

In a memristor crossbar array, functioning as a memory array, a memristor is positioned on each row–column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this paper, we study the sneak path problem in crossbar arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are modeling the error channel induced by sneak paths, a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method, we match a constraint on the array content that guarantees sneak-path free readout, determine the resulting capacity, and provide an efficient encoder that achieves the capacity. [ABSTRACT FROM PUBLISHER]

Volume of metric balls relates to rate-distortion theory and packing bounds on codes. In this paper, the volume of balls in complex Grassmann manifolds is evaluated for an arbitrary radius. The ball is defined as a set of hyperplanes of a fixed dimension with reference to a center of possibly different dimensions, and a generalized chordal distance for unequal dimensional subspaces is used. First, the volume is reduced to a 1-D integral representation. The overall problem boils down to evaluating a determinant of a matrix of the same size as the subspace dimensionality. Interpreting this determinant as a characteristic function of the Jacobi ensemble, an asymptotic analysis is carried out. The obtained asymptotic volume is moreover refined using moment-matching techniques to provide a tighter approximation in finite-size regimes. Finally, the pertinence of the derived results is shown by rate-distortion analysis of source coding on Grassmann manifolds. [ABSTRACT FROM PUBLISHER]

Bent functions can be classified into regular bent functions, weakly regular but not regular bent functions, and non-weakly regular bent functions. Regular and weakly regular bent functions always appear in pairs, since their duals are also bent functions. In general, this does not apply to non-weakly regular bent functions. However, the first known construction of non-weakly regular bent functions by Çeşmelioğlu et al. yields bent functions for which the dual is also bent. In this paper, the first construction of non-weakly regular bent functions for which the dual is not bent is presented. We call such functions non-dual-bent functions. Until now, only sporadic examples found via computer search were known. We then show that with the direct sum of bent functions and with the construction by Çeşmelioğlu et al., one can obtain infinitely many non-dual-bent functions once one example of a non-dual-bent function is known. [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

In this paper, we show that the secrecy function conjecture that states that the maximum of the secrecy function of an l -modular lattice occurs at 1/\sqrt {l} is false, by proving that the four-modular lattice C^{(4)}= \mathbb {Z}\oplus \sqrt {2} \mathbb {Z}\oplus 2 \mathbb {Z} fails to satisfy this conjecture. After this, we indicate how the secrecy function must be modified in the l -modular case to provide a more meaningful comparison for l -modular lattices, and show that this new secrecy function indeed has a maximum at for various two-modular lattices and for C^(4) . We conjecture that this must hold true for all l -modular lattices. [ABSTRACT FROM PUBLISHER]

This paper investigates the first- and second-order maximum achievable rates of codes with/without cost constraints for mixed channels whose channel law is characterized by a general mixture of (at most) uncountably many stationary and memoryless discrete channels. These channels are referred to as mixed memoryless channels with general mixture and include the class of mixed memoryless channels of finitely or countably memoryless channels as a special case. For the mixed memoryless channels with general mixture, the first-order coding theorem which gives a formula for the $\varepsilon $ -capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios. [ABSTRACT FROM PUBLISHER]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. Strictly optimal FHSs are those FHSs with optimal partial Hamming autocorrelation irrespective of the correlation window length. In this paper, strictly optimal FHSs are investigated from a combinatorial approach. A generic connection between strictly optimal FHSs and disjoint cyclic perfect Mendelsohn difference families is established. By virtue of this connection, new strictly optimal FHSs are generated from some disjoint CPMDFs. These strictly optimal FHSs have new parameters not covered in the literature. [ABSTRACT FROM AUTHOR]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth’s achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters. [ABSTRACT FROM PUBLISHER]

The Vandermonde decomposition of Toeplitz matrices, discovered by Carathéodory and Fejér in the 1910s and rediscovered by Pisarenko in the 1970s, forms the basis of modern subspace methods for 1-D frequency estimation. Many related numerical tools have also been developed for multidimensional (MD), especially 2-D, frequency estimation; however, a fundamental question has remained unresolved as to whether an analog of the Vandermonde decomposition holds for multilevel Toeplitz matrices in the MD case. In this paper, an affirmative answer to this question and a constructive method for finding the decomposition are provided when the matrix rank is lower than the dimension of each Toeplitz block. A numerical method for searching for a decomposition is also proposed when the matrix rank is higher. The new results are applied to study the MD frequency estimation within the recent super-resolution framework. A precise formulation of the atomic \ell 0 norm is derived using the Vandermonde decomposition. Practical algorithms for frequency estimation are proposed based on the relaxation techniques. Extensive numerical simulations are provided to demonstrate the effectiveness of these algorithms compared with the existing atomic norm and subspace methods. [ABSTRACT FROM AUTHOR]

Multi-permutations and in particular permutations appear in various applications in an information theory. New applications, such as rank modulation for flash memories, have suggested the need to consider error-correcting codes for multi-permutations. In this paper, we study systematic error-correcting codes for multi-permutations in general and for permutations in particular. For a given number of information symbols k , and for any integer t , we present a construction of (k+r,k) systematic t -error-correcting codes, for permutations of length $k+r$ , where the number of redundancy symbols $r$ is relatively small. In particular, for a given $t$ and for sufficiently large $k$ , we obtain $r=t+1$ , while a lower bound on the number of redundancy symbols is shown to be $t$ . The same construction is also applied to obtain related systematic error-correcting codes for any types of multi-permutations. [ABSTRACT FROM AUTHOR]

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert–Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets. [ABSTRACT FROM AUTHOR]

The quantum relative entropy between two states satisfies a monotonicity property meaning that applying the same quantum channel to both states can never increase their relative entropy. It is known that this inequality is only tight when there is a recovery map that exactly reverses the effects of the quantum channel on both states. In this paper, we strengthen this inequality by showing that the difference of relative entropies is bounded below by the measured relative entropy between the first state and a recovered state from its processed version. The recovery map is a convex combination of rotated Petz recovery maps and perfectly reverses the quantum channel on the second state. As a special case, we reproduce recent lower bounds on the conditional mutual information, such as the one proved by Fawzi and Renner. Our proof only relies on the elementary properties of pinching maps and the operator logarithm. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6. [ABSTRACT FROM AUTHOR]

We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem—the minimal compression rate and the error exponent—were found in a previous work, in this paper, we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: the gain (amplitude) of the vector is compressed via scalar quantization, and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated, and they converge to the asymptotic values, as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice. [ABSTRACT FROM AUTHOR]

Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on 5 \times 3 = 15 variables that are invariant under the actions of the cyclic group {GF(2^{5})}^\ast \,{\cdot }\, {GF(2^{3})}^\ast as well as the group of Frobenius automorphisms. Some of these Boolean functions possess nonlinearity greater than the bent concatenation bound. The next possible option for exploring such functions is on 7 \times 3 = 21$ variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for the first time. [ABSTRACT FROM AUTHOR]

Free will (or randomness) has been studied to achieve loophole-free Bell’s inequality test and to provide device-independent quantum key distribution security proofs. The required randomness such that a local hidden variable model (LHVM) can violate the Clauser–Horne–Shimony–Holt (CHSH) inequality has been studied, but a tight bound has not been proved for a practical case that: 1) the device settings of the two parties in the Bell test are independent and 2) the device settings of each party can be correlated or biased across different runs. Using some information theoretic techniques, we prove, in this paper, a tight bound on the required randomness for this case, such that the CHSH inequality can be violated by certain LHVM. Our proof has a clear achievability and converse style. The achievability part is proved using type counting. To prove the converse part, we introduce a concept called profile for a set of binary sequences and study the properties of profiles. Our profile-based converse technique is also of independent interest. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computation capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. A new upper bound is derived that is tighter than cut-set-based and genie-aided bounds. A matching inner bound is established via the development of a network decomposition theorem, which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually simple proof of achievability that generalizes to $L$ -transmitter $L$ -receiver networks. [ABSTRACT FROM AUTHOR]

We consider a communication system in which status updates arrive at a source node, and should be transmitted through a network to the intended destination node. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of the information available to the destination node is the time elapsed, since the last received update was generated. In this paper, we model the source-destination link using the queuing theory, and we assume that the time it takes to successfully transmit a packet to the destination is an exponentially distributed service time. We analyze the age of information in the case that the source node has the capability to manage the arriving samples, possibly discarding packets in order to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update. [ABSTRACT FROM AUTHOR]

The relevance in a sampling theory of U -invariant subspaces of a Hilbert space \mathcal {H} , where U denotes a unitary operator on \mathcal H , is nowadays a recognized fact. Indeed, shift-invariant subspaces of L^2(\mathbb R) become a particular example; periodic extensions of finite signals also provide a remarkable example. As a consequence, the availability of an abstract $U$ -sampling theory becomes a useful tool to handle these problems. In this paper, we derive a sampling theory for finite dimensional multiple generated $U$ -invariant subspaces of a Hilbert space \mathcal {H} . As the involved samples are identified as frame coefficients in a suitable euclidean space, the relevant mathematical technique is that of the finite frame theory. Since finite frames are nothing but spanning sets of vectors, the used technique naturally meets matrix analysis. [ABSTRACT FROM AUTHOR]

Opportunistic detection rules (ODRs) are variants of fixed-sample-size detection rules in which the statistician is allowed to make an early decision on the alternative hypothesis opportunistically based on the sequentially observed samples. From a sequential decision perspective, ODRs are also mixtures of one-sided and truncated sequential detection rules. Several results regarding ODRs are established in this paper. In the finite regime, the maximum sample size is modeled either as a fixed finite number, or a geometric random variable with a fixed finite mean. For both cases, the corresponding Bayesian formulations are investigated. The former case is a slight variation of the well-known finite-length sequential hypothesis testing procedure in the literature, whereas the latter case is new, for which the Bayesian optimal ODR is shown to be a sequence of likelihood ratio threshold tests with two different thresholds. A running threshold, which is determined by solving a stationary state equation, is used when future samples are still available, and a terminal threshold (simply the ratio between the priors scaled by costs) is used when the statistician reaches the final sample and, thus, has to make a decision immediately. In the asymptotic regime, the tradeoff among the exponents of the (false alarm and miss) error probabilities and the normalized expected stopping time under the alternative hypothesis is completely characterized and proved to be tight, via an information-theoretic argument. Within the tradeoff region, one noteworthy fact is that the performance of the Stein-Chernoff lemma is attainable by ODRs. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH , the corresponding minimum pair distance is at least dH+3 . In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH , the minimum pair distance is at least dH +\left \lceil{ {dH/{2}}}\right \rceil . We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, $b \geqslant 3$ , of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting. [ABSTRACT FROM AUTHOR]

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. A permutation \sigma \in Sn satisfies the single-neighbor $k$ -constraint if \sigma (i+1)-\sigma (i)\leq k$ for all 1\leq i\leq n-1$ . In this paper, this model is extended into two constraints. A permutation k$ -constraint if for all 2 \leq i \leq n-1$ , \sigma (i)-\sigma (i-1)\leq k$ or \sigma (i \,\, + \,\, 1)-\sigma (i)\leq k$ , and it satisfies the asymmetric two-neighbor k$ -constraint if for all 2 \leq i \leq n-1$ , and the capacity of the second constraint is 1 regardless for any positive $k$ . We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall $\tau $ -metric. [ABSTRACT FROM AUTHOR]

Non-malleable codes, introduced by Dziembowski et al., encode messages s in a manner, so that tampering the codeword causes the decoder to either output s or a message that is independent of s . While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family of tampering functions that is not too large (for instance, when | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{a}}\alpha n}} for some \alpha <1 , where n is the number of bits in a codeword). In this paper, we study the capacity of non-malleable codes, and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. Specifically, We prove that for every family \mathcal {F} with | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{}}\alpha n}} , there exist non-malleable codes against \mathcal F with rate arbitrarily close to 1-\alpha [this is achieved with high probability (w.h.p.) by a randomized construction]. We show the existence of families of size \exp (n^O(1) 2^\alpha n) against which there is no non-malleable code of rate $1-\alpha $ (in fact this is the case w.h.p for a random family of this size). We also show that 1-\alpha $ is the best achievable rate for the family of functions, which are only allowed to tamper the first \alpha n$ bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword, a model which has received some attention recently) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 of size 2^{n^{c}} , in particular tampering functions with, say, cubic size circuits. [ABSTRACT FROM PUBLISHER]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

It is known that the majority of the human genome consists of duplicated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from duplicated sequences and has mutated to its current form. In this paper, we investigate the possibility of constructing an exponentially large number of sequences from a short initial sequence using simple duplication rules, including those resembling genomic-duplication processes. In other words, our goal is to find the capacity, or the expressive power, of these string-duplication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-duplication systems. The study of these fundamental biologically inspired systems is an important step toward modeling and analyzing more complex biological processes. [ABSTRACT FROM AUTHOR]

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed–Solomon (GRS) codes is proved to be co-NP-complete by Guruswami and Vardy. For the extended Reed–Solomon codes RSq( \mathbb {F}q,k) , a conjecture was made to classify deep holes by Cheng and Murray. Since then efforts have been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for GRS codes RSp (D,k) , where $p$ is a prime, |D| > k \geqslant ({p-1})/{2} . Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös–Heilbronn conjecture. [ABSTRACT FROM PUBLISHER]

This paper studies the mismatched decoding problem for binary-input discrete memoryless channels. An example is provided for which an achievable rate based on superposition coding exceeds the Csiszár-Körner-Hui rate, thus providing a counter-example to a previously reported converse result. Both numerical evaluations and theoretical results are used in establishing this claim. [ABSTRACT FROM PUBLISHER]

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums. [ABSTRACT FROM AUTHOR]

Scalable frames are frames with the property that the frame vectors can be rescaled resulting in tight frames. However, if a frame is not scalable, one has to aim for an approximate procedure. For this, in this paper we introduce three novel quantitative measures of the closeness to scalability for frames in finite dimensional real Euclidean spaces. Besides the natural measure of scalability given by the distance of a frame to the set of scalable frames, another measure is obtained by optimizing a quadratic functional, while the third is given by the volume of the ellipsoid of minimal volume containing the symmetrized frame. After proving that these measures are equivalent in a certain sense, we establish bounds on the probability of a randomly selected frame to be scalable. In the process, we also derive new necessary and sufficient conditions for a frame to be scalable. [ABSTRACT FROM PUBLISHER]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

The optical orthogonal codes (OOCs) have been widely used as spreading codes in communication systems employing the unipolar transmission. They are classified into constant-weight OOCs (CW-OOCs) and variable-weight OOCs (VW-OOCs) according to the number of distinct Hamming weights which their codewords have. In this paper, we present a new generic construction of VW-OOCs of length $(q-1)N$ from a CW-OOC of length $N$ , where $q$ is a prime power and $\gcd (q-1,N)=1$ . As a result, three new families of optimal VW-OOCs with a maximum correlation value 1 are obtained. In particular, these families can have the codewords of high weights, while most of the previously known optimal VW-OOCs have only codewords of weight less than 8. [ABSTRACT FROM PUBLISHER]

This paper provides new constructions and lower bounds for subspace codes, using Ferrers diagram rank-metric codes from matchings of the complete graph and pending blocks. We present different constructions for constant dimension codes with minimum injection distance 2 or $k-1$ , where $k$ is the constant dimension. Furthermore, we present a construction of new codes from old codes for any minimum distance. Then, we construct nonconstant dimension codes from these codes. Some examples of codes obtained by these constructions are the largest known codes for the given parameters. [ABSTRACT FROM PUBLISHER]

Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string $X$ of length $n$ under $t$ deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string $X$ ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of $r$ -run strings $X$ , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every $r$ , we present $r$ -run strings with the minimum (respectively maximum) number of subsequences under any $t$ deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time. [ABSTRACT FROM AUTHOR]