Search

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

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

The most commonly used setting in the coded caching literature consists of the following four elements: (i) homogeneous file sizes, (ii) homogeneous cache sizes, (iii) user-independent homogeneous file popularity (i.e., all users share the same file preference), and (iv) worst-case rate analysis. While recent results have relaxed some of these assumptions, deeper understanding of the full heterogeneity setting is still much needed since traditional caching schemes place little assumptions on file/cache sizes and almost always allow each user to have his/her own file preference through individualized file request prediction. Taking a microscopic approach, this paper characterizes the exact capacity of the smallest 2-user/2-file ($N=K=2$) problem but under the most general setting that simultaneously allows for (i) heterogeneous files sizes, (ii) heterogeneous cache sizes, (iii) user-dependent file popularity, and (iv) average-rate analysis. Solving completely the case of $N=K=2$ could shed further insights on the performance and complexity of optimal coded caching with full heterogeneity for arbitrary $N$ and $K$. [ABSTRACT FROM AUTHOR]

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules. [ABSTRACT FROM AUTHOR]

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops $m$ , the transmission time $n$ , and the error probability. We introduce a simple, efficient, and deterministic protocol that attains positive information velocity (i.e., a non-vanishing ratio $\frac {m}{n}$ and small error probability) and is significantly simpler than existing protocols that do so. In addition, we characterize the optimal low-noise and high-noise scaling laws of the information velocity, and we adapt our 1-bit protocol to transmit $k$ bits over $m$ hops with $\mathcal {O}(m+k)$ transmission time. [ABSTRACT FROM AUTHOR]

$\mathbb {Z}_{2^{s}}$ -additive codes are subgroups of $\mathbb {Z}^{n}_{2^{s}}$ , and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{2^{s}}$ -linear code is a binary code (not necessarily linear) which is the Gray map image of a $\mathbb {Z}_{2^{s}}$ -additive code. We consider $\mathbb {Z}_{2^{s}}$ -additive simplex codes of type $\alpha $ and $\beta $ , which are a generalization over $\mathbb {Z}_{2^{s}}$ of the binary simplex codes. These codes are related to the $\mathbb {Z}_{2^{s}}$ -additive Hadamard codes. In this paper, we use this relationship to find a linear subcode of the corresponding $\mathbb {Z}_{2^{s}}$ -linear codes, called kernel, and a representation of these codes as cosets of this kernel. In particular, this also gives the linearity of these codes. Similarly, $\mathbb {Z}_{2^{s}}$ -additive MacDonald codes are defined for $s>2$ , and equivalent results are obtained. [ABSTRACT FROM AUTHOR]

Nonconvex constraints are valuable regularizers in many optimization problems. In particular, sparsity constraints have had a significant impact on sampling theory, where they are used in compressed sensing and allow structured signals to be sampled far below the rate traditionally prescribed. Nearly, all of the theory developed for compressed sensing signal recovery assumes that samples are taken using linear measurements. In this paper, we instead address the compressed sensing recovery problem in a setting where the observations are nonlinear. We show that, under conditions similar to those required in the linear setting, the iterative hard thresholding algorithm can be used to accurately recover sparse or structured signals from few nonlinear observations. Similar ideas can also be developed in a more general nonlinear optimization framework. In the second part of this paper, we therefore present related result that shows how this can be done under sparsity and union of subspaces constraints, whenever a generalization of the restricted isometry property traditionally imposed on the compressed sensing system holds. [ABSTRACT FROM PUBLISHER]

This paper studies the distinctness of primitive sequences over \bf Z/(M) modulo 2, where M is an odd integer that is composite and square-free, and \bf Z/(M) is the integer residue ring modulo M. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomial f\left(x\right) over \bf Z/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper, and consequently, the set of primitive sequences over \bf Z/(M) that can be proven to be distinct modulo 2 is greatly enlarged. [ABSTRACT FROM PUBLISHER]

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

In this paper, we investigate the convergence speed of the Arimoto-Blahut algorithm. For many channel matrices, the convergence speed is exponential, but for some channel matrices it is slower than exponential. By analyzing the Taylor expansion of the defining function of the Arimoto-Blahut algorithm, we will make the conditions clear for the exponential or slower convergence. The analysis of the slow convergence in this paper is new. Based on this analysis, we will compare the convergence speeds of the Arimoto-Blahut algorithm numerically with the values obtained in our theorems for several channel matrices. The purpose of this paper is to obtain a complete understanding of the convergence speed of the Arimoto-Blahut algorithm. [ABSTRACT FROM AUTHOR]

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

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

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

Both linear complementary dual (LCD) codes and maximum distance separable (MDS) codes have good algebraic structures, and they have interesting practical applications such as communication systems, data storage, quantum codes, and so on. So far, most of LCD MDS codes have been constructed by employing generalized Reed-Solomon codes. In this paper we construct some classes of new Euclidean LCD MDS codes and Hermitian LCD MDS codes which are not monomially equivalent to Reed-Solomon codes, called LCD MDS codes of non-Reed-Solomon type. Our method is based on the constructions of Beelen et al. (2017) and Roth and Lempel (1989). To the best of our knowledge, this is the first paper on the construction of LCD MDS codes of non-Reed-Solomon type; any LCD MDS code of non-Reed-Solomon type constructed by our method is not monomially equivalent to any LCD code constructed by the method of Carlet et al. (2018). [ABSTRACT FROM AUTHOR]

Barcoding photons, atoms, and any quantum states can provide a host of functionalities that could benefit future quantum communication systems and networks beyond today’s imagination. As a significant application of barcoding photons, we introduce code division multiple-access (CDMA) communication systems for various applications. In this context, we introduce and discuss the fundamental principles of a novel quantum CDMA (QCDMA) technique based on spectrally encoding and decoding of continuous-mode quantum light pulses. In particular, we present the mathematical models of various QCDMA modules that are fundamental in describing an ideal and typical QCDMA system, such as quantum signal sources, quantum spectral encoding phase operators, M × M quantum broadcasting star-coupler, quantum spectral phase decoding operators, and the quantum receivers. Following the above discussions, we then elaborate on a QCDMA system with M users. In describing a QCDMA system, this paper considers a unified approach where the input continuous-mode quantum light pulses can take on any form of pure states such as quantum coherent (Glauber) states and quantum number (Fock) states. The mathematical presentation is independent of the form of the input pure quantum states. We show that the spectrally encoded quantum states of the light at the quantum star-coupler output are not, in general, factorized states, except for input Glauber states. For input number states, one can observe features like entanglement and quantum interference. Moreover and interestingly, as a consequence of Heisenberg’s uncertainty principle, the quantum signals sent by photon number states obtain complete phase uncertainty at the time of measurement. Therefore, at the receiver output, the multiaccess inter-signal interference vanishes. Due to Heisenberg’s uncertainty principle, the received signal intensity at the photodetector’s output, right at the time of measurement, changes from coherent detection scheme for input Glauber states to incoherent detection scheme for input number states. We also would like to highlight that the mathematical models and tools developed in this paper, in the context of QCDMA, become very useful for developing and analyzing other quantum multiple-access techniques based on wavelength, space and time domain. Furthermore, our mathematical model is valuable in signal design and data modulations of point-to-point quantum communications, quantum pulse shaping, and quantum radar signals and systems where the inputs are continuous mode quantum signals. QCDMA may open up novel possibilities for various quantum technologies such as data privacy, distributed quantum computation, quantum internet, and anti-jamming quantum communication systems. [ABSTRACT FROM AUTHOR]

This paper studies a memoryless state-dependent multiple access channel (MAC) where two transmitters wish to convey a message to a receiver under the assumption of causal and imperfect channel state information at transmitters (CSIT) and imperfect channel state information at receiver (CSIR). In order to emphasize the limitation of transmitter cooperation between physically distributed nodes, we focus on the so-called distributed CSIT assumption, i.e., where each transmitter has its individual channel knowledge, while the message can be assumed to be partially or entirely shared a priori between transmitters by exploiting some on-board memory. Under this setup, the first part of the paper characterizes the common message capacity of the channel at hand for arbitrary CSIT and CSIR structure. The optimal scheme builds on Shannon strategies, i.e., optimal codes are constructed by letting the channel inputs be a function of current CSIT only. For a special case when CSIT is a deterministic function of CSIR, the considered scheme also achieves the capacity region of a common message and two private messages. The second part addresses an important instance of the previous general result in a context of a cooperative multi-antenna Gaussian channel under i.i.d. fading operating in frequency-division duplex mode, such that CSIT is acquired via an explicit feedback of perfect CSIR. The capacity of the channel at hand is achieved by distributed linear precoding applied to Gaussian codes. Surprisingly, we demonstrate that it is suboptimal to send a number of data streams bounded by the number of transmit antennas as typically considered in a centralized CSIT setup. Finally, numerical examples are provided to evaluate the sum capacity of the binary MAC with binary states as well as the Gaussian MAC with i.i.d. fading. [ABSTRACT FROM AUTHOR]

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

This paper studies large scatter matrix estimation for heavy tailed distributions. The contributions of this paper are twofold. First, we propose and advocate to use a new distribution family, the pair-elliptical, for modeling the high dimensional data. The pair-elliptical is more flexible and easier to check the goodness of fit compared to the elliptical. Secondly, built on the pair-elliptical family, we advocate using quantile-based statistics for estimating the scatter matrix. For this, we provide a family of quantile-based statistics. They outperform the existing ones for better balancing the efficiency and robustness. In particular, we show that the propose estimators have comparable performance to the moment-based counterparts under the Gaussian assumption. The method is also tuning-free compared to Catoni’s M-estimator for covariance matrix estimation. We further apply the method to conduct a variety of statistical methods. The corresponding theoretical properties as well as numerical performances are provided. [ABSTRACT FROM AUTHOR]

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

The article discusses brief profile of several awardees of the 2013 IEEE Information Theory Society Paper Award including Shrinivas Kudekar, Thomas J. Richardson and Rüdiger L. Urbanke. Kadoka has completed his bachelor's degree in electrical engineering from the Indian Institute Of Technology (IIT) in Bombay, India in 2003, Richardson is working as vice-president at Semiconductors Company Qualcomm Inc. and Urbane is involved in designing of iterative coding schemes.

The article discusses brief profile of several awardees of the 2013 IEEE Communications Society and Information Theory Society Joint Paper Award including Salman Avestimehr, Bobak Nazer and Michael Gastpar. Gastpar has served as an associate editor for shannon theory for the journal. Nazer has received various awards such as the Dean's Catalyst Award, the NSF CAREER Award and the Eli Jury Award. Gatspar is working as an adjunct associate professor at the University of California, Berkeley.

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

This paper studies reconstruction of strings based upon their substrings spectrum. Under this paradigm, it is assumed that all substrings of some fixed length are received and the goal is to reconstruct the string. While many existing works assumed that substrings are received error free, we follow in this paper the noisy setup of this problem that was first studied by Gabrys and Milenkovic. The goal of this study is twofold. First we study the setup in which not all substrings in the multispectrum are received, and then we focus on the case where the read substrings are not error free. In each case we provide specific code constructions of strings that their reconstruction is guaranteed even in the presence of failure in either model. We present efficient encoding and decoding maps and analyze the cardinality of the code constructions, while studying the cases where the rates of our codes approach 1. [ABSTRACT FROM AUTHOR]

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance. [ABSTRACT FROM AUTHOR]

In this paper, we consider a general K-user Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC). We assume that the channel state is deterministic and known to all the nodes. While the private-message capacity region is well known to be achievable with dirty paper coding (DPC), we are interested in the simpler linearly precoded transmission schemes. In particular, we focus on linear precoding schemes combined with rate-splitting (RS). First, we derive an achievable rate region with minimum mean square error (MMSE) precoding at the transmitter and joint decoding of the sub-messages at the receivers. Then, we study the achievable sum rate of this scheme and obtain two findings: 1) an analytically tractable upper bound on the sum rate that is shown numerically to be a close approximation, and 2) how to reduce the number of active streams – crucial to the overall complexity – while preserving the sum rate to within a constant loss. The latter results in two practical algorithms: a stream elimination algorithm and a stream ordering algorithm. Finally, we investigate the constant-gap optimality of linearly precoded RS with respect to the capacity. Our result reveals that, while the achievable rate of linear precoding alone can be arbitrarily far from the capacity, the introduction of RS can help achieve the capacity region to within a constant gap in the two-user case. Nevertheless, we prove that the RS scheme’s constant-gap optimality does not extend to the three-user case. Specifically, we show, through a pathological example, that the gap between the sum rate and the sum capacity can be unbounded. [ABSTRACT FROM AUTHOR]

In this paper, we apply two-to-one functions over F2n in two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t + x)e with gcd (t, n) = gcd(e, 2n−1) = 1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters. [ABSTRACT FROM AUTHOR]

The inverse function x → x−1 on F2n, is one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x−1) + L2(x) over F2n if n ≥ 5, where L1,L2 are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics. [ABSTRACT FROM AUTHOR]

One objective of this paper is to propose a novel class of sequence pairs, called “quasi-orthogonal Z-complementary pairs (QOZCPs)”, each depicting Z-complementary property for their aperiodic auto-correlation sums and also having a low correlation zone when their aperiodic cross-correlation is considered. Construction of QOZCPs based on Successively Distributed Algorithms under Majorization Minimization (SDAMM) is presented. Another objective of this paper is to apply the proposed QOZCPs in fully polarimetric radar systems and analyse the corresponding ambiguity functions. It turns out that QOZCP waveforms are much more Doppler resilient than the known Golay complementary waveforms. [ABSTRACT FROM AUTHOR]

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure a Boolean function’s resistance to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. Some of the binary LCD codes presented in this paper are optimal. These binary LCD codes have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems. [ABSTRACT FROM AUTHOR]

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

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

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide several constructions, some of which are shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is order-wise equivalent to the amount required in the classical error correcting paradigm. [ABSTRACT FROM AUTHOR]

The article announces Institute of Electrical and Electronics Engineers's (IEEE) Information Theory Society Paper Award given to various authors including 2011 IEEE Information Theory Society Paper Award to Masahito Hayashi and 2008 and 2010 Best Student Paper Awards to Yury Polyanskiy.

This paper investigates the secret-key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Over multiple rounds of communication, the adversary first decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the goal of the adversary being to have the decoder accept and decode their observation as a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret-key-authenticated-capacity region here is then defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the first of a two-part study, with the parts differing in their measure of the authentication rate. In this first study, the authentication rate is the exponent of blocklength-normalized exponent of the expected probability of false authentication. For this metric, we provide an inner bound which improves on those existing in the literature. This is achieved by adopting and merging different classical techniques in novel ways. Within these classical secret-key-based authentication techniques, one technique derives authentication capability from secure channel coding to send the secret key with the message, and the other technique derives its authentication capability directly from obscuring the source. [ABSTRACT FROM AUTHOR]

In this paper, we determine all dihedral subgroups in $PGL_{2}(\mathbb {F}_{q})$ , where $q=2^{l}$ and $l$ is a positive integer; and construct binary expurgated and extended Goppa codes with dihedral automorphism groups. Moreover, it is easy to obtain binary quasi-cyclic expurgated or extended Goppa codes. [ABSTRACT FROM AUTHOR]

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios. [ABSTRACT FROM AUTHOR]

Let $\mathbf {X}\in \mathbb {C}^{n\times m}$ ($m\geq n$) be a random matrix with independent columns each distributed as complex multivariate Gaussian with zero mean and single-spiked covariance matrix $\mathbf {I}_{n}+ \eta \mathbf {u}\mathbf {u}^{*}$ , where $\mathbf {I}_{n}$ is the $n\times n$ identity matrix, $\mathbf {u}\in \mathbb {C}^{n\times 1}$ is an arbitrary vector with unit Euclidean norm, $\eta \geq 0$ is a non-random parameter, and $(\cdot)^{*}$ represents the conjugate-transpose. This paper investigates the distribution of the random quantity $\kappa _{\text {SC}}^{2}(\mathbf {X})=\sum _{k=1}^{n} \lambda _{k}/\lambda _{1}$ , where $0\le \lambda _{1}\le \lambda _{2}\le \ldots \leq \lambda _{n} < \infty $ are the ordered eigenvalues of $\mathbf {X}\mathbf {X}^{*}$ (i.e., single-spiked Wishart matrix). This random quantity is intimately related to the so called scaled condition number or the Demmel condition number (i.e., $\kappa _{\text {SC}}(\mathbf {X})$) and the minimum eigenvalue of the fixed trace Wishart-Laguerre ensemble (i.e., $\kappa _{\text {SC}}^{-2}(\mathbf {X})$). In particular, we use an orthogonal polynomial approach to derive an exact expression for the probability density function of $\kappa _{\text {SC}}^{2}(\mathbf {X})$ which is amenable to asymptotic analysis as matrix dimensions grow large. Our asymptotic results reveal that, as $m,n\to \infty $ such that $m-n$ is fixed and when $\eta $ scales on the order of $1/n$ , $\kappa _{\text {SC}}^{2}(\mathbf {X})$ scales on the order of $n^{3}$. In this respect we establish simple closed-form expressions for the limiting distributions. It turns out that, as $m,n\to \infty $ such that $n/m\to c\in (0,1)$ , properly centered $\kappa _{\text {SC}}^{2}(\mathbf {X})$ fluctuates on the scale $m^{\frac {1}{3}}$. [ABSTRACT FROM AUTHOR]

A vertex subset $S$ of a graph $G$ constitutes a 1-perfect code if the one-balls centered at the nodes in $S$ effect a vertex partition of $G$. This paper considers the quad-cube $CQ_{m}$ that is a connected $(m+2)$ -regular spanning subgraph of the hypercube $Q_{4m+2}$ , and shows that $CQ_{m}$ admits a vertex partition into 1-perfect codes iff $m=2^{k}-3$ , where $k\ge 2$. The scheme for that purpose makes use of a procedure by Jha and Slutzki that constructs Hamming codes using a Latin square. The result closely parallels the existence of a 1-perfect code over the dual-cube, which is another derivative of the hypercube. [ABSTRACT FROM AUTHOR]

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

This article studies the zero-error feedback capacity of causal discrete channels with memory. First, by extending the classical zero-error feedback capacity concept, a new notion of uniform zero-error feedback capacity $C_{0f} $ for such channels is introduced. Using this notion a tight condition for bounded stabilization of unstable noisy linear systems via causal channels is obtained, assuming no channel state information at either end of the channel. Furthermore, the zero-error feedback capacity of a class of additive noise channels is investigated. It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback is equal $\log q-\mathcal {H}_{ch} $ , where $\mathcal {H}_{ch} $ is the entropy rate of the noise process and $q $ is the input alphabet size. In this paper, for a class of finite-state additive noise channels (FSANCs), it is shown that the zero-error feedback capacity is either zero or $C_{0f} =\log q -h_{ch} $ , where $h_{ch} $ is the topological entropy of the noise process. A condition is given to determine when the zero-error capacity with or without feedback is zero. This, in conjunction with the stabilization result, leads to a “Small-Entropy Theorem”, stating that stabilization over FSANCs can be achieved if the sum of the topological entropies of the linear system and the channel is smaller than $\log q$. [ABSTRACT FROM AUTHOR]

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as $O\left({\sqrt {\frac{k \log n }{ m}}}\right)$ , where $k$ , $m$ and $n$ denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as $O\left({{\frac{k \log n }{ m}}}\right)$ , suggests that if the signal class is structured (i.e., $k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp. [ABSTRACT FROM AUTHOR]

Faced with massive data, subsampling is a commonly used technique to improve computational efficiency, and using nonuniform subsampling probabilities is an effective approach to improve estimation efficiency. For computational efficiency, subsampling is often implemented with replacement or through Poisson subsampling. However, no rigorous investigation has been performed to study the difference between the two subsampling procedures such as their estimation efficiency and computational convenience. This paper performs a comparative study on these two different sampling procedures. In the context of maximizing a general target function, we first derive asymptotic distributions for estimators obtained from the two sampling procedures. The results show that the Poisson subsampling may have a higher estimation efficiency. Based on the asymptotic distributions for both subsampling with replacement and Poisson subsampling, we derive optimal subsampling probabilities that minimize the variance functions of the subsampling estimators. These subsampling probabilities further reveal the similarities and differences between subsampling with replacement and Poisson subsampling. The theoretical characterizations and comparisons on the two subsampling procedures provide guidance to select a more appropriate subsampling approach in practice. Furthermore, practically implementable algorithms are proposed based on the optimal structural results, which are evaluated through both theoretical and empirical analyses. [ABSTRACT FROM AUTHOR]

Detection of the number of signals corrupted by high-dimensional noise is a fundamental problem in signal processing and statistics. This paper focuses on a general setting where the high-dimensional noise has an unknown complicated heterogeneous variance structure. We propose a sequential test which utilizes the edge singular values (i.e., the largest few singular values) of the data matrix. It also naturally leads to a consistent sequential testing estimate of the number of signals. We describe the asymptotic distribution of the test statistic in terms of the Tracy-Widom distribution. The test is shown to be accurate and have full power against the alternative, both theoretically and numerically. The theoretical analysis relies on establishing the Tracy-Widom law for a large class of Gram type random matrices with non-zero means and completely arbitrary variance profiles, which can be of independent interest. [ABSTRACT FROM AUTHOR]

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex $X$ at layer 0, and $k + 1$ vertices at layer $k \geq 1$ , which are at a distance of $k$ from $X$. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, $X$ is given a uniform random bit. At time $k \geq 1$ , each vertex in layer $k$ receives transmitted bits from its parents in layer $k-1$ , where the bits pass through independent binary symmetric channels with common crossover probability $\delta \in \left({0,\frac {1}{2}}\right)$ during the process of transmission. Then, each vertex at layer $k$ with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover $X$ with probability of error better than $\frac {1}{2}$ from all vertices at layer $k$ as $k \rightarrow \infty $. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time $k$ to $k+1$. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level $\delta $ and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of $X$ is impossible for any $\delta \in \left({0,\frac {1}{2}}\right)$ provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering $X$ for any $\delta \in \left({0,\frac {1}{2}}\right)$ when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of $\delta $ via linear programming. [ABSTRACT FROM AUTHOR]

The recent success of generative adversarial networks and variational learning suggests that training a classification network may work well in addressing the classical two-sample problem, which asks to differentiate two densities given finite samples from each one. Network-based methods have the computational advantage that the algorithm scales to large datasets. This paper considers using the classification logit function, which is provided by a trained classification neural network and evaluated on the testing set split of the two datasets, to compute a two-sample statistic. To analyze the approximation and estimation error of the logit function to differentiate near-manifold densities, we introduce a new result of near-manifold integral approximation by neural networks. We then show that the logit function provably differentiates two sub-exponential densities given that the network is sufficiently parametrized, and for on or near manifold densities, the needed network complexity is reduced to only scale with the intrinsic dimensionality. In experiments, the network logit test demonstrates better performance than previous network-based tests using classification accuracy, and also compares favorably to certain kernel maximum mean discrepancy tests on synthetic datasets and hand-written digit datasets. [ABSTRACT FROM AUTHOR]

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

Let $q\geq 2$ be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension $k$ in $\mathbb {F}_{q}^{n}$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in $n$) to the cumulative distribution function of the minimum of $(q^{k}-1)/(q-1)$ independent binomial random variables with parameters $\frac {1}{q}$ and $n$. The latter, in turn, converges to a Gumbel distribution at integer points when $\frac {k}{n}$ converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert–Varshamov bound for $2< q< 49$. [ABSTRACT FROM AUTHOR]

Minimizing the divergence between two probability distributions offers an alternative parameter estimation method. The current literature mainly focuses on minimizing the Kullback-Leibler (K-L) divergence between the true and the proposed models in which the true model is assumed to be known or fixed. In this paper, we propose a parameter estimation method that minimizes the $f$ -divergence between two probability distributions. The method is suitable for different situations, no matter the true distribution is known or not. The statistical properties of the estimator, including consistency and asymptotic normality, are established. As an illustration, our method is employed to estimate the degradation model, which is a model frequently used to assess the lifetime of highly reliable products. A simulation study and a real degradation data analysis are presented to illustrate the effectiveness of the proposed estimation method. [ABSTRACT FROM AUTHOR]