Search

One-bit compressed sensing (1bCS) is an extremely quantized signal acquisition method that has been proposed and studied rigorously in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized to only one bit per sample (sign of the measurement). The extreme quantization makes it an interesting case study of the more general single-index or generalized linear models. At the same time it can also be thought of as a ‘design’ version of learning a binary linear classifier or halfspace-learning. Assuming the original signal vector to be sparse, existing results in 1bCS either aim to find the support of the vector, or approximate the signal allowing a small error. The focus of this paper is support recovery, which often also computationally facilitate approximate signal recovery. A universal measurement matrix for 1bCS refers to one set of measurements that work for all sparse signals. With universality, it is known that $\tilde {\Theta }(k^{2})~1$ bCS measurements are necessary and sufficient for support recovery (where $k$ denotes the sparsity). To improve the dependence on sparsity from quadratic to linear, in this work we propose approximate support recovery (allowing $\epsilon >0$ proportion of errors), and superset recovery (allowing $\epsilon $ proportion of false positives). We show that the first type of recovery is possible with $\tilde {O}(k/\epsilon )$ measurements, while the later type of recovery, more challenging, is possible with $\tilde {O}(\max \{k/\epsilon ,k^{3/2}\}) ^{^{^{^{}}}}$ measurements. We also show that in both cases $\Omega (k/\epsilon )$ measurements would be necessary for universal recovery. Improved results are possible if we consider universal recovery within a restricted class of signals, such as rational signals, or signals with bounded dynamic range. In both cases superset recovery is possible with only $\tilde {O}(k/\epsilon )$ measurements. Other results on universal but approximate support recovery are also provided in this paper. All of our main recovery algorithms are simple and polynomial-time.

This paper studies a class of stochastic and time-varying Gaussian intersymbol interference (ISI) channels. The probability law for the $i^{th}$ channel tap during time slot $t$ is supported over an interval of centre $c_{i}$ and radius $r_{i}$ . The transmitter and the receiver only know the centres $c_{i}$ and the radii $r_{i}$ . The joint distribution for the array of channel taps and their realizations are unknown to both the transmitter and the receiver. A lower bound (achievability result) is presented on the channel capacity which results in an upper bound on the capacity loss compared to when all radii are zeros. The lower bound on the channel capacity saturates at a positive value as the maximum average input power $P$ increases beyond what is referred to as the saturation power $P_{sat}$ . Roughly speaking, $P_{sat}$ is inversely proportional to the sum of the squares of the radii $r_{i}$ . It is also verified that in the presence of channel state information at the receiver, if the so-called central channel frequency response is everywhere nonzero, then the aforementioned capacity loss is bounded from above by a constant that does not depend on $P$ . A partial converse result is provided in a scenario where different channel taps vary independently of each other and each channel tap process is stationary with a finite differential entropy rate. It is shown that for every sequence of codebooks with vanishing probability of error, if the size of each symbol in every codeword is bounded away from zero by a constant that is proportional to $\sqrt {P}$ , then the rate of that sequence of codebooks does not scale with $P$ . Tools in matrix analysis such as matrix norms and Weyl’s inequality on perturbation of eigenvalues of symmetric matrices are used in order to analyze the probability of error. A result in the paper that may find other applications is a new and tight upper bound on the size of a Gaussian typical set.

Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky-Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.

This paper investigates the privacy problem in coded caching. Recently, it was shown that the seminal MAN coded caching scheme leaks the demand information of each user to the other users in the system. Many works have considered coded caching with demand privacy, while every non-trivial existing coded caching scheme with private demands was built on the fact that the cache information of each user is private to the others. However, most of these schemes leak the users’ cache information. As a consequence, in most realistic settings (e.g., video streaming) where the system is used over time with multiple sequential transmission rounds, these schemes leak demand privacy beyond the first round. This observation motivates our new formulation of coded caching with simultaneously private demands and caches in this paper. For this new model, we first show that an existing coded caching scheme with private demands, referred to as the virtual users scheme, can also preserve the privacy of the users’ caches. However, this scheme suffers from its extremely high subpacketization. The main contribution of this paper is a new construction that generates private coded caching schemes by leveraging two-server private information retrieval (PIR) schemes. We show that if in the PIR scheme the demand is uniform over all files and the queries are independent, the resulting caching scheme is private on both the demands and the caches; otherwise, the resulting scheme is private only on the demands. This first result constructs coded caching schemes from a particular class of PIR schemes, which is a new “structural” result in its own merit. We then construct new two-server PIR schemes with uniform demand and independent queries, such that the resulting caching scheme has a subpacketization level that is significantly reduced compared to the virtual users scheme. Interestingly we propose a new construction of two-server PIR schemes with uniform demand and independent queries by exploiting coded caching schemes. By applying the seminal Maddah-Ali and Niesen coded caching scheme in our construction, the resulting two-server PIR scheme is proved to be order-optimal under the constraint of uniform demand and independent queries. This is a second new “structural” result that somehow closes the loop in the relationship between coded caching and PIR. As a by-product of our new construction, we obtain a new demand private that improves the load of the state-of-the-art demand private caching schemes known so far. Finally, to explore a broader tradeoff between cache privacy and transmission load, we relax the cache privacy constraint and introduce the definition of cache information leakage. Then, again as a by-product of our new construction, we propose new schemes with perfect demand privacy and imperfect cache privacy that achieve an order-gain in load with respect to the scheme with perfect privacy on both demands and caches. This also establishes a first non-trivial achievability result in the tradeoff between load and cache privacy, for demand-private caching schemes.

ABS polar codes were recently proposed to speed up polarization by swapping certain pairs of adjacent bits after each layer of polar transform. In this paper, we observe that applying the Arıkan transform $(U_{i}, U_{i+1}) \mapsto (U_{i}+U_{i+1}, U_{i+1})$ on certain pairs of adjacent bits after each polar transform layer leads to even faster polarization. In light of this, we propose ABS+ polar codes which incorporate the Arıkan transform in addition to the swapping transform in ABS polar codes. In order to efficiently construct and decode ABS+ polar codes, we derive a new recursive relation between the joint distributions of adjacent bits through different layers of polar transforms. Simulation results over a wide range of parameters show that the CRC-aided SCL decoder of ABS+ polar codes improves upon that of ABS polar codes by $0.1 \mathop {\mathrm {dB}}\nolimits $ – $0.25 \mathop {\mathrm {dB}}\nolimits $ while maintaining the same decoding time. Moreover, ABS+ polar codes improve upon standard polar codes by $0.2 \mathop {\mathrm {dB}}\nolimits $ – $0.45 \mathop {\mathrm {dB}}\nolimits $ when they both use the CRC-aided SCL decoder with list size 32. The implementations of all the algorithms in this paper are available at https://github.com/PlumJelly/ABS-Polar

Constructing Reed–Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. Our focus in this paper is on the special case of two-dimensional RS-codes that can correct from $n-3$ insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known that an $[n], [2]_{q}$ RS-code that can correct from $n-3$ insdel errors satisfies that $q=\Omega (n^{3})$ . On the other hand, there are several known constructions of $[n], [2]_{q}$ RS-codes that can correct from $n-3$ insdel errors, where the smallest field size is $q=O(n^{4})$ . In this short paper, we construct $[n], [2]_{q}$ Reed–Solomon codes that can correct $n-3$ insdel errors with $q=O(n^{3})$ , thereby resolving the minimum field size needed for such codes.

Subfield codes of linear codes over finite fields have recently received much attention since they can produce optimal codes, which may have applications in secret sharing, authentication codes and association schemes. In this paper, we first present a construction framework of 3-dimensional linear codes ${\mathcal{ C}}_{f,g}$ over $\mathbb {F}_{q^{m}}$ parameterized by any two functions $f, g$ over $\mathbb {F}_{q^{m}}$ , and then study the properties of six types of ${\mathcal{ C}}_{f,g}$ , its punctured code ${\mathcal{ C}}^{\ast}_{f,g}$ and their corresponding subfield codes over $\mathbb {F}_{q}$ . The classification of ${\mathcal{ C}}_{f,g}$ is based on special choices of $f,g$ as trace function, norm function, almost bent function, Boolean bent function or a combination of these functions. For the first two types of ${\mathcal{ C}}_{f,g}$ , we explicitly determine the weight distributions and dualities of ${\mathcal{ C}}_{f,g}, {\mathcal{ C}}_{f,g}^{\ast}$ and their subfield codes over $\mathbb {F}_{q}$ . The remaining four types of ${\mathcal{ C}}_{f,g}$ are restricted to $q=2$ , and the weight distributions and dualities of the subfields code ${\mathcal{ C}}_{f,g}^{(q)}$ and ${\cal C_{f,g}^{\ast}}^{(q)}$ are completely determined. Most of the resultant linear codes (over $\mathbb {F}_{q^{m}}$ or over $\mathbb {F}_{q}$ ) have few weights. Some of them are optimal and some have the best-known parameters according to the tables maintained at https://www.codetables.de. In fact, 16 infinite families of optimal linear codes are produced in this paper. As a byproduct, a family of $[2^{4m-2},2m+1,2^{4m-3}]$ quaternary Hermitian self-orthogonal codes are obtained with $m \geq 2$ . As an application, we present several infinite families of 2-designs or 3-designs with some of the codes presented in this paper.

In this paper, we propose a data-driven parameters’ adaptation technique for Stochastic Dynamic Neural Field (SDNF) models with finite signal transmission rate modeled by a distance-dependent delay. Our approach integrates nonlinear Bayesian filtering methods into mathematical neuroscience by establishing the state-space representation for the SDNF models with the delays. This allows to formulate the filtering problem in order to reconstruct the average membrane potential from incomplete data available from measurement devices. Additionally, when the state-space model is set up, the unknown system parameters can be estimated in a systematic way, for example, by using the method of maximum likelihood. In this paper, we derive for the first time the SDNF-oriented adaptive Extended Kalman filter (EKF) with the space-dependent delays in order to calibrate the SDNF models and to reconstruct the average membrane potential from incomplete data collected. The main benefit of the novel methodology is that both problems–the state and parameter estimation–are solved in parallel. The numerical experiments are provided to illustrate a performance of the novel methodology.

Cyclic codes are important in theory, as they are closely related to a number of areas of mathematics. Cyclic codes are also important in practice, as they have efficient encoding and decoding algorithms. An infinite family of cyclic codes over ${\mathrm {GF}}(q)$ is said to have linearly-best-known parameters if for any $[n, k, d]$ code ${\mathcal {C}}$ in this family, there is no known $[n, k, d']$ linear code over ${\mathrm {GF}}(q)$ such that $d' > d$ . An infinite family of cyclic codes over ${\mathrm {GF}}(q)$ is said to have cyclicly-best-known parameters if for any $[n, k, d]$ code ${\mathcal {C}}$ in this family, there is no known $[n, k, d']$ cyclic code over ${\mathrm {GF}}(q)$ such that $d' > d$ . It is very rare to see an infinite family of binary cyclic codes with cyclicly-best-known parameters whose duals codes have also cyclicly-best-known parameters. The objective of this paper is to study such family of binary cyclic codes of length $2^{m}-1$ and dimension $2^{m}-1-m(m-1)/2$ , denoted by ${\mathcal {C}}_{(2,m,2)}$ , and their dual codes ${\mathcal {C}}_{(2,m,2)}^{\perp} $ . The weight distribution of ${\mathcal {C}}_{(2,m,2)}^{\perp} $ is settled and the parameters of ${\mathcal {C}}_{(2,m,2)}$ are investigated in this paper. A larger family of binary cyclic codes ${\mathcal {C}}_{(2,m,r)}$ and their duals are also constructed and studied in this paper, where $0 \leq r \leq m-1$ .

Since its development, the minimax framework has been one of the corner stones of theoretical statistics, and has contributed to the popularity of many well-known estimators, such as the regularized M-estimators for high-dimensional problems. In this paper, we will first show through the example of sparse Gaussian sequence model, that the theoretical results under the classical minimax framework are insufficient for explaining empirical observations. In particular, both hard and soft thresholding estimators are (asymptotically) minimax, however, in practice they often exhibit sub-optimal performances at various signal-to-noise ratio (SNR) levels. The first contribution of this paper is to demonstrate that this issue can be resolved if the signal-to-noise ratio is taken into account in the construction of the parameter space. We call the resulting minimax framework the signal-to-noise ratio aware minimaxity. The second contribution of this paper is to showcase how one can use higher-order asymptotics to obtain accurate approximations of the SNR-aware minimax risk and discover minimax estimators. The theoretical findings obtained from this refined minimax framework provide new insights and practical guidance for the estimation of sparse signals.

Constacyclic codes contain cyclic codes as a subclass and have nice algebraic structures. Constacyclic codes have theoretical importance, as they are connected to a number of areas of mathematics and outperform cyclic codes in several aspects. Negacyclic codes are a subclass of constacyclic codes and are distance-optimal in many cases. However, compared with the extensive study of cyclic codes, negacyclic codes are much less studied. In this paper, several families of ternary negacyclic codes and their duals are constructed and analysed. These families of negacyclic codes and their duals contain distance-optimal codes and have very good parameters in general. The duals of three families of ternary negacyclic codes presented in this paper are distance-optimal.

Twisted Generalized Reed-Solomon (TGRS) Codes are a class of linear codes which contain MDS codes but are not equivalent to GRS code. In recent years, many scholars have studied the construction of MDS self-dual codes through TGRS code. Among these works, the number of twists is actually quite small, and an important step in showing a TGRS code is self-dual is to find its parity-check matrix. In this paper, we focus on the computation of parity-check matrices of TGRS codes with almost no restrictions on twist and hook vectors. By application of elementary row (column) operations in linear algebra, we present a unified but elementary approach to obtain the parity-check matrices of TGRS codes. This paper creates a foundation for further study of MDS self-dual TGRS codes on a much broader scope.

Average consensus is a key component of multi-agent systems coordination, while data privacy becomes a serious concern. Through the information exchange process, the initial state of an agent may be disclosed to its neighbors. The existing privacy-preserving research mainly addressed the situation of single-neighbor eavesdropping and infinite-time consensus, and they cannot deal with the cases of multi-neighbors eavesdropping and collusion inference attack or ensuring finite-time consensus. In this paper, we prove that it is impossible to preserve a node’s data privacy if all of its neighbors collusively infer the data. Otherwise, we propose a privacy-preserving framework to support conventional average consensus, push-sum consensus, and finite-time average consensus, which integrates multiplying random variables, finite-time error compensation, and updating rule jump. In this paper, each agent exchanges data with its neighbors by multiplying a random variable to its real-time state at each iteration. To eliminate errors caused by the random multiplier, a finite-time error compensation term and updating rule jump are designed, which ensure the accuracy of consensus. We prove that the proposed framework can converge and preserve privacy facing collusion inference attacks in both finite-time and infinite-time consensus, while traditional adding-noise-based methods cannot solve the finite-time case. We also derive the analytical expressions of the maximum privacy disclosure probability for the initial state of each agent, and present the impact of multiplying random variables. Extensive case studies demonstrate the effectiveness of the proposed framework.

In this paper, we study the type graph, namely, a bipartite graph induced by a joint type. We investigate the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale in the length $n$ of the type. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the length of the type goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of $(R_{1},R_{2})$ such that there exists a biclique of the type graph which has respectively $2^{nR_{1}}$ and $2^{nR_{2}}$ vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We then discuss the connections of these results to noninteractive simulation and hypercontractivity inequalities. Furthermore, as an application of our results, a new outer bound for the zero-error capacity region of the binary adder channel is provided, which improves the previously best known bound, due to Austrin, Kaski, Koivisto, and Nederlof. Our proofs in this paper are based on the method of types and linear algebra.

A power assignment over Gaussian broadcast channels splits the power budget at the access point among all user-channel pairs subject to per-channel upper-bounds on the sum-power, and is optimal if it maximizes the weighted sum-rate (WSR). In this paper we first present a geometric algorithm for computing an optimal power assignment over single Gaussian broadcast channel, which has linear complexity if all users are presorted either by weight or by noise. We also provide an intuitively appealing water-filling interpretation of this geometric algorithm. By leveraging such water-filling interpretation, we develop a water-filling algorithm for computing an optimal power assignment over parallel Gaussian broadcast channels, whose complexity is linear in the number of user-channel pairs if all users are presorted by weight. From these algorithmic studies, we derive clean and simple expressions of the maximum WSR in both integral forms and sum forms. By exploiting the rich property of those forms, we further give a linear-complexity algorithm for computing a power budget at the access point, subject to a given upper bound, which maximizes the difference between the maximum WSR and a linear cost of the power budget. The algorithmic studies in this paper also reveal that a single Gaussian broadcast channel can be decomposed into parallel Gaussian single-user channels which preserve the maximum WSR.

A promising approach to deal with the high hardware cost and energy consumption of massive MIMO transmitters is to use low-resolution digital-to-analog converters (DACs) at each antenna element. This leads to a transmission scheme where the transmitted signals are restricted to a finite set of voltage levels. This paper is concerned with the analysis and optimization of a low-cost quantized precoding strategy, referred to as linear-quantized precoding, for a downlink massive MIMO system under Rayleigh fading. In linear-quantized precoding, the signals are first processed by a linear precoding matrix and subsequently quantized component-wise by the DAC. In this paper, we analyze both the signal-to-interference-plus-noise ratio (SINR) and the symbol error probability (SEP) performances of such linear-quantized precoding schemes in an asymptotic framework where the number of transmit antennas and the number of users grow large with a fixed ratio. Our results provide a rigorous justification for the heuristic arguments based on the Bussgang decomposition that are commonly used in prior works. Based on the asymptotic analysis, we further derive the optimal precoder within a class of linear-quantized precoders that includes several popular precoders as special cases. Our numerical results demonstrate the excellent accuracy of the asymptotic analysis for finite systems and the optimality of the derived precoder.

In this paper an approach to joint source-channel coding (JSCC) named Shannon-Kotel’nikov (S-K) mappings is discussed. S-K mappings are continuous, or piecewise smooth direct source-to-channel mappings operating on amplitude-continuous and discrete-time signals, and they encompass several existing JSCC schemes as special cases. Many existing approaches to analog- or hybrid discrete-analog JSCC provide both excellent performance as well as robustness to variable noise level at both low and arbitrary complexity and delay. However, a general theory explaining their performance and behaviour, as well as guidelines on how to construct well-performing mappings, do not exist. Therefore, such mappings are often based on educated guesses inspired by configurations that are known in advance to produce good solutions through numerical optimization methods. The objective of this paper is to develop a theoretical framework for analysis of analog- or hybrid discrete-analog S-K mappings which enables calculation of distortion when applying them on point-to-point links, reveal more about their fundamental nature, and provide guidelines for their construction at low as well as arbitrary complexity and delay. Such guidelines will likely help constrain solutions to numerical approaches and help explain why deep learning approaches obtain the solutions they do. The overall task is difficult and we do not provide a complete framework at this stage: We focus on high SNR and memoryless sources with an arbitrary continuous unimodal density function and memoryless Gaussian channels. We also provide example mappings based on surfaces which are chosen, or constructed, based on the provided theory.

This paper studies a novel multi-access coded caching (MACC) model in the two-dimensional (2D) topology, which is a generalization of the one-dimensional (1D) MACC model proposed by Hachem et al. The 2D MACC model is formed by a server containing $N$ files, $K_{1}\times K_{2}$ cache-nodes with $M$ files located at a grid with $K_{1}$ rows and $K_{2}$ columns, and $K_{1}\times K_{2}$ cache-less users where each user is connected to $L^{2}$ nearby cache-nodes. The server is connected to the users through an error-free shared link, while the users can retrieve the cached content of the connected cache-nodes without cost. Our objective is to minimize the worst-case transmission load over all possible users’ demands. In this paper, we first propose a grouping scheme for the case where $K_{1}$ and $K_{2}$ are divisible by $L$ . By partitioning the cache-nodes and users into $L^{2}$ groups such that no two users in the same group share any cache-node, we use the shared-link coded caching scheme proposed by Maddah-Ali and Niesen for each group. Then for any model parameters satisfying $\min \{K_{1},K_{2}\}\geq L$ , we propose a transformation approach which constructs a 2D MACC scheme from two classes of 1D MACC schemes in vertical and horizontal projections, respectively. As a result, we can construct 2D MACC schemes that achieve maximum local caching gain and improved coded caching gain, compared to the baseline scheme by a direct extension from 1D MACC schemes. In addition, we propose new information theoretic converse bounds under the uncoded placement constraint by leveraging the network topology.

This paper investigates the information theoretic limit of a reconfigurable intelligent surface (RIS) aided communication scenario in which the RIS and the transmitter either jointly or independently send information to the receiver. The RIS is an emerging technology that uses a large number of passive reflective elements with adjustable phases to intelligently reflect the transmit signal to the intended receiver. While most previous studies of the RIS focus on its ability to beamform and to boost the received signal-to-noise ratio (SNR), this paper shows that if the information data stream is also available at the RIS and can be modulated through the adjustable phases at the RIS, significant improvement in the degree-of-freedom (DoF) of the overall channel is possible. For example, for an RIS system in which the signals are reflected from a transmitter with $M$ antennas to a receiver with $K$ antennas through an RIS with $N$ reflective elements, assuming no direct path between the transmitter and the receiver, joint transmission of the transmitter and the RIS can achieve a DoF of $\min \left({M+\frac {N}{2}-\frac {1}{2},N,K}\right)$ as compared to the DoF of $\min (M,K)$ for the conventional multiple-input multiple-output (MIMO) channel. This result is obtained by establishing a connection between the RIS system and the MIMO channel with phase noise and by using results for characterizing the information dimension under projection. The result is further extended to the case with a direct path between the transmitter and the receiver, and also to the multiple access scenario, in which the transmitter and the RIS send independent information. Finally, this paper proposes a symbol-level precoding approach for modulating data through the phases of the RIS, and provides numerical simulation results to verify the theoretical DoF results.

In this paper, we put forward secure network function computation over a directed acyclic network. In such a network, a sink node is required to compute with zero error a target function of which the inputs are generated as source messages at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a security function of the source messages. The secure computing capacity for the above model is defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node with the given collection of wiretap sets and security function for one use of the network. The characterization of this capacity is in general overwhelmingly difficult. In the current paper, we consider securely computing linear functions with a wiretapper who can eavesdrop any subset of edges up to a certain size $r$ , referred to as the security level, with the security function being the identity function. We first prove an upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. This upper bound depends on the network topology and security level. Furthermore, we obtain an upper bound and a lower bound on this bound, which are both in closed form. In particular, when the security level $r$ is equal to 0, our upper bound reduces to the computing capacity without security consideration. Also, we discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. Furthermore, we obtain an equivalent expression of the upper bound by using a graph-theoretic approach, and accordingly we develop an efficient approach for computing this bound. On the other hand, we present a construction of linear function-computing secure network codes and obtain a lower bound on the secure computing capacity. By our code construction, for the linear function which is over a given finite field, we can always construct a (vector-) linear function-computing secure network code over the same field. We also give some sufficient conditions for the tightness of the lower bound in terms of the network topology. With this lower bound and the upper bound we have obtained, the secure computing capacity for some classes of secure models can be fully characterized. Another interesting case is that the security function is the same as the target function, which will be investigated in Part II of this paper.

Geometric path-loss (GPL) in the radio propagation channel dominantly decides the signal strength and hence yields a significant and multi-faceted influence on wireless communications and networking. In this paper, the GPL is reported to be (truncated) Pareto distributed in wireless random networks, which applies to both of the two considered cases: locally random network (LRN) and homogeneous random network (HRN). Note that most literature assume (infinite) HRNs for scenarios of the fourth or earlier generation wireless communication where most base stations (BSs) have the omni-directional coverage. This might easily be violated when there exist node clusters and, more importantly, for 5G or beyond scenarios with mmWave or THz communication that are more narrow directional on the beamforming and hence coverage. However, the node clusters can reasonably be modelled by the LRNs, thus solving the above issue. To cope with that, the LRN is considered to be more generic and hence easily reduces to the HRN. Two applications on the path-loss exponent (PLE) self-estimation and the expected interference are also presented to demonstrate the significance of this contribution. The findings in this paper might cast light upon the future of random network analysis and designing new kinds of techniques.

Constacyclic codes over finite fields are a family of linear codes and contain cyclic codes as a subclass. Constacyclic codes are related to many areas of mathematics and outperform cyclic codes in several aspects. Hence, constacyclic codes are of theoretical importance. On the other hand, constacyclic codes are important in practice, as they have rich algebraic structures and may have efficient decoding algorithms. In this paper, two classes of constacyclic codes are constructed using a general construction of constacyclic codes with cyclic codes. The first class of constacyclic codes is motivated by the punctured Dilix cyclic codes and the second class is motivated by the punctured generalised Reed-Muller codes. The two classes of constacyclic codes contain optimal linear codes. The parameters of the two classes of constacyclic codes are analysed and some open problems are presented in this paper.

Cyclically permutable codes (CPCs) have found important applications in many communication systems, such as the multiple access collision channel without feedback, frequency-hopping spread spectrum communication channels and the digital watermarking systems. In this paper, by introducing a new method we completely settle the problem of constructing a CPC with the largest possible code size derived from a given simple-root cyclic code. The contribution of this paper is twofold. First, we present a new enumerative formula for the code size of such CPC with all the terms being positive integers, contrasting to the previously known ones given in Allard et al. (1973), Song et al. (1993), Tavares et al. (1971), and Xia and Fu (1997) which involve the Möbius function. Second, we provide an algebraic and systematic method to produce such a CPC. Several examples are also included to illustrate our main results.

BCH codes and their dual codes are two special subclasses of cyclic codes and are the best linear codes in many cases. A lot of progress on the study of BCH cyclic codes has been made, but little is known about the minimum distances of duals of BCH codes. Recently, a concept called dually-BCH code was introduced to investigate the duals of BCH codes and the lower bounds on their minimum distances in Gong et al., (2022). For a prime power $q$ and an integer $m \ge 4$ , let $n=\frac {q^{m}-1}{q+1}$ ( $m$ even), or $n=\frac {q^{m}-1}{q-1}$ ( $q>2$ ). In this paper, some sufficient and necessary conditions in terms of the designed distance will be given to ensure that the narrow-sense BCH codes of length $n$ are dually-BCH codes, which extended the results in Gong et al., (2022). Lower bounds on the minimum distances of their dual codes are developed for $n=\frac {q^{m}-1}{q+1}$ ( $m$ even). As byproducts, we present the largest coset leader $\delta _{1}$ modulo $n$ being of two types, which proves a conjecture in Wu et al., (2019) and partially solves an open problem in Li et al., (2017). We also investigate the parameters of narrow-sense BCH codes of length $n$ with design distance $\delta _{1}$ . The BCH codes presented in this paper have good parameters in general.

In this paper, we revisit the Rank Quasi-Cyclic (RQC) (Melchor et al., IEEE IT, 2018) encryption scheme by proposing three possible variations for its design. Our first improvement relies on the introduction of Augmented Gabidulin codes, a new family of decodable codes exploiting the concept of support erasure for the rank metric. Following the work of Melchor et al. (PQCrypto, 2022), our second improvement uses multiple syndromes to increase the weight of the error to be decoded. As pioneered in Melchor et al. (NIST PQC, 2020), our third variation considers non-homogeneous error weights in order to decrease the parameters. These improvements can be combined together to design schemes offering various trade-offs in term of security and size. Our Multi-UR-AG (multiple syndromes, unstructured, augmented Gabidulin) scheme achieves a size of 11kB (public key + ciphertext) for 128 bits of security while featuring a conservative design as it relies on pure random instances without any ideal structure. Besides, our NH- Multi-RQC-AG (non-homogeneous error, multiple syndromes, ideal structure, augmented Gabidulin) achieves a size of 2.7 kB for 128 bits of security, namely a 50 % improvement with respect to classical RQC. Our second and third variations respectively rely on the security of the $\textsf {RSL} $ and $\textsf {NHRSD} $ problems (or $\textsf {NHRSL} $ when considered together). In this paper, we also provide new security analysis and attacks for these problems. While these results are important for our new schemes, they are of independent interest as well. Our security analysis for the $\textsf {RSL} $ problem provides an improvement on the recent algebraic attacks for some instances. In addition, we show that the $\textsf {RSL} $ problem can be solved in polynomial time when $N \geq (k+1) r\frac {m}{m-r}$ , this improves the best known combinatorial attack (Gaborit et al., Crypto, 2017). We also propose the first combinatorial attack against the $\textsf {NHRSD} $ problem along with a precise complexity analysis of the algebraic attack described Melchor et al. (NIST PQC, 2020). At last, we combine these analysis to provide an attack against the $\textsf {NHRSL} $ problem.

The Permuted Kernel Problem (PKP) asks to find a permutation which maps an input matrix into the kernel of some given vector space. The literature exhibits several works studying its hardness in the case of the input matrix being mono-dimensional (i.e., a vector), while the multi-dimensional case has received much less attention and, de facto, only the case of a binary ambient finite field has been studied. The Subcode Equivalence Problem (SEP), instead, asks to find a permutation so that a given linear code becomes a subcode of another given code. At the best of our knowledge, no algorithm to solve the SEP has ever been proposed. In this paper we study the computational hardness of solving these problems. We first show that, despite going by different names, PKP and SEP are exactly the same problem. Then we consider the state-of-the-art solver for the mono-dimensional PKP (namely, the KMP algorithm, proposed by Koussa, Macario-Rat and Patarin), generalize it to the multi-dimensional case and analyze both the finite and the asymptotic regimes. We further propose a new algorithm, which can be thought of as a refinement of KMP. In the asymptotic regime our algorithm does not improve on KMP but, in the finite regime (and for parameters of practical interest), we achieve significant improvements, especially for the multi-dimensional version of PKP. As an evidence, we show that it is the fastest algorithm to attack several recommended instances of cryptosystems based on PKP. As a side-effect, given the mentioned equivalence between PKP and SEP, all the algorithms we analyze in this paper can be used to solve instances of the latter problem.

The paper presents exponentially-strong converses for source-coding, channel coding, and hypothesis testing problems. More specifically, it presents alternative proofs for the well-known exponentially-strong converse for almost lossless source-coding with side-information and for channel coding over a discrete memoryless channel (DMC). These alternative proofs are solely based on a change of measure argument on the sets of conditionally or jointly-typical sequences that result in a correct decision, and on the analysis of these measures in the asymptotic regime of infinite blocklengths. The paper also presents new exponentially-strong converses for the $K$ -hop hypothesis testing against independence problem with certain Markov chains and for the two-terminal $L$ -round interactive compression problem with $J\geq 1$ distortion constraints that depend on both sources and both reconstructions. For this latter problem, the exponentially-strong converse result states that whenever the rates lie outside the vanishing-excess-distortion-probability rate-region, then the sum of the $J$ excess distortion probabilities asymptotically exceeds 1 or tends to 1 exponentially fast in the blocklength. (When the sum of the excess distortion probabilities exceeds 1, then a larger rate-distortion region is shown to be achievable.) The considered $L$ -round $J$ -distortion interactive source coding problem includes as special cases the Wyner-Ziv problem, the interactive function computation problem, and the compression with lossy common reconstruction problem. The new strong converse proofs for lossy compression and distributed hypothesis testing are derived using similar change of measure arguments as mentioned earlier and by additionally proving that certain Markov chains involving auxiliary random variables hold in the asymptotic regime of infinite blocklengths.

The literature provides evidence that considering signal propagation delays can significantly enhance the scheduling rate region of wireless networks. This paper focuses on the link scheduling problem in networks where signal delays between nodes are multiples of a time interval. To model such networks, a directed hypergraph is employed, along with an integer matrix that specifies the delays. The link scheduling problem is closely connected to the independent sets of the periodic hypergraph induced by the network model. However, due to the infinite number of vertices, it is impractical to enumerate the independent sets of the periodic hypergraph using generic graph algorithms. To tackle this challenge, a graphical approach is proposed in this paper. The link scheduling rate region is characterized using a finite directed graph called a scheduling graph, which is derived from the network model. A collision-free schedule of the network corresponds to a path in the scheduling graph, and the rate region is determined by the convex hull of the rate vectors associated with the cycles in the scheduling graph. Although existing cycle enumeration algorithms can be employed to calculate the rate region, their computational complexity becomes prohibitively high as the size of the scheduling graph grows exponentially with the number of network links. To address this issue, the dominance property of a special scheduling graph called the step- $T$ scheduling graph is investigated. This property allows the utilization of specific subgraphs of the step- $T$ scheduling graph to characterize the scheduling rate region, achieving a reduction in both the number of cycles and their lengths. For common problems such as calculating the rate region and maximizing a weighted sum of the scheduling rates, algorithms leveraging the dominance property are developed. These algorithms can be more efficient than using generic graph algorithms directly on the scheduling graphs.

This paper introduces the concept of projective essential idempotents. These are primitive central idempotents in a twisted group algebra. The first main result provides conditions for the existence of them. In the second main result, we prove that every q-ary simplex code can be seen as an ideal of a twisted group algebra generated by a projective essential idempotent. We conclude by describing a decoding process using projective essential idempotents.

A communication setup is considered where a single transmitter wishes to convey messages to one or two receivers and simultaneously estimate the states of the receivers through the backscattered signals of the emitted waveform. The scenario at hand is motivated by joint radar and communication, which aims to co-design radar sensing and communication over shared spectrum and hardware. In this paper, we model the communication channel as a simple memoryless channel with independent and identically distributed (i.i.d.) time-varying state sequences and we model the backscattered signals by (strictly causal) generalized feedback. For single-receiver systems of this form, we fully characterize the capacity-distortion tradeoff, defined as the largest rate at which a message can reliably be conveyed to the receiver while simultaneously allowing the transmitter to sense the state sequence with a given allowed distortion. Our results show a tradeoff between the achievable rates and distortions, and that this tradeoff only stems from a common choice of the input distribution (the waveform) but not from other properties of the utilized codes. To better illustrate the capacity-distortion tradeoff, we propose a numerical method to compute the optimal inputs (waveforms) that achieve the desired tradeoff. For two-receiver systems with two states, we characterize the capacity-distortion tradeoff region of physically degraded broadcast channels (BC) as a rather straightforward extension of the single receiver case. Here, a tradeoff not only arises between sensing and communication performances but also between the various rates and the distortions of the different states. Similarly to the single-receiver case, the optimal co-design scheme exploits the generalized feedback signals only for sensing but not for improving communication performance. This is different for general two-receiver BCs, where optimal co-design schemes exploit generalized feedback also to improve capacity. However, as we show, also for BCs the optimal sensing performance only depends on the chosen input distribution (waveform) but not on the code construction used to accomplish the communication task. For general BCs, we provide inner and outer bounds on the capacity-distortion region, as well as a sufficient condition when this capacity-distortion region is equal to the product of the capacity region and the set of achievable distortions, in which case no tradeoff between sensing and communication occurs. A number of illustrative examples demonstrate that the optimal co-design schemes outperform conventional schemes that split the resources between sensing and communication, both for single-receiver and BC systems.

Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csiszár, Körner, Lovász, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same. Furthermore, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.

This paper investigates the concept of self-dual convolutional codes. We derive the basic properties of this interesting class of codes and we show how some of the techniques to construct self-dual linear block codes generalize to self-dual convolutional codes. As for self-dual linear block codes we are able to give a complete classification for some small parameters.

Adversarial examples have recently drawn considerable attention in the field of machine learning due to the fact that small perturbations in the data can result in major performance degradation. This phenomenon is usually modeled by a malicious adversary that can apply perturbations to the data in a constrained fashion, such as being bounded in a certain norm. In this paper, we study this problem when the adversary is constrained by the $\ell _{0}$ norm; i.e., it can perturb a certain number of coordinates in the input, but has no limit on how much it can perturb those coordinates. Due to the combinatorial nature of this setting, we need to go beyond the standard techniques in robust machine learning to address this problem. We consider a binary classification scenario where $d$ noisy data samples of the true label are provided to us after adversarial perturbations. We introduce a classification method which employs a nonlinear component called truncation, and show in an asymptotic scenario, as long as the adversary is restricted to perturb no more than $\sqrt {d}$ data samples, we can almost achieve the optimal classification error in the absence of the adversary, i.e., we can completely neutralize adversary’s effect. Surprisingly, we observe a phase transition in the sense that using a converse argument, we show that if the adversary can perturb more than $\sqrt {d}$ coordinates, no classifier can do better than a random guess.

This paper considers the performance of Reed–Muller (RM) codes transmitted over binary memoryless symmetric (BMS) channels under bitwise maximum-a-posteriori (bit-MAP) decoding. Its main result is that, for a fixed BMS channel, the family of binary RM codes can achieve a vanishing bit-error probability at rates approaching the channel capacity. This partially resolves a long-standing open problem that connects information theory and error-correcting codes. In contrast with the earlier result for the binary erasure channel, the new proof does not rely on hypercontractivity. Instead, it combines a nesting property of RM codes with new information inequalities relating the generalized extrinsic information transfer function and the extrinsic minimum mean-squared error.

In the paper, the Levenshtein’s sequence reconstruction problem is considered in the case where the transmitted words are chosen from an $e$ -error-correcting code, at most $t$ substitution errors occur in each of the $N$ channels and the decoder outputs a list of length $\mathcal {L}$ . Previously, when $t = e+\ell $ and the transmitted word is long enough, the numbers of required channels were determined for $\mathcal {L}=1, 2~\text {and }~\ell +1$ . Here we determine the exact number of channels in the cases $\mathcal {L}= 3, 4, \ldots, \ell $ . This also provides the size of the largest intersection of $\mathcal {L}$ balls of radius $t$ (with respect to substitutions) centered at the words with mutual Hamming distances at least $2e+1$ . Furthermore, with the aid of covering codes, we also consider the list sizes in the cases where the length $n$ is rather small (improving previously known results). After that we study how much we can decrease the number of required channels when we use list-decoding codes. Finally, the majority algorithm is discussed for decoding in a probabilistic set-up; in particular, we show that the output word of the decoder can be verified to be the transmitted one with high probability.

In this paper, we characterize the generalized degrees-of-freedom (GDoF) region of the two-user $(M,N_{1},N_{2})$ multiple-input multiple-output (MIMO) broadcast channel with delayed channel state information at the transmitter (CSIT), where there are one transmitter with $M$ antennas and two receivers with $N_{1}$ and $N_{2}$ antennas, respectively. Under delayed CSIT, different from the existing converse approaches in the multiple-input single-output (MISO) GDoF and MIMO degrees-of-freedom (DoF) models, we incorporate new components into traditional approaches for this MIMO GDoF converse. For the achievability, we generalize the existing MISO achievable scheme. Our result reveals how the channel strength and antenna configuration impact the GDoF region of the two-user MIMO broadcast channel with delayed CSIT. Furthermore, the extension of our converse to a GDoF outer region of the $K$ -user MIMO broadcast channel with delayed CSIT is also provided.

The Bayesian Context Trees (BCT) framework is a recently introduced, general collection of statistical and algorithmic tools for modelling, analysis and inference with discrete-valued time series. The foundation of this development is built in part on some well-known information-theoretic ideas and techniques, including Rissanen’s tree sources and Willems et al.’s context-tree weighting algorithm. This paper presents a collection of theoretical results that provide mathematical justifications and further insight into the BCT modelling framework and the associated practical tools. It is shown that the BCT prior predictive likelihood (the probability of a time series of observations averaged over all models and parameters) is both pointwise and minimax optimal, in agreement with the MDL principle and the BIC criterion. The posterior distribution is shown to be asymptotically consistent with probability one (over both models and parameters), and asymptotically Gaussian (over the parameters). And the posterior predictive distribution is also shown to be asymptotically consistent with probability one.

We investigate the problem of private read-update-write (PRUW) in relation to private federated submodel learning (FSL), where a machine learning model is divided into multiple submodels based on the different types of data used to train the model. In PRUW, each user downloads the required submodel without revealing its index in the reading phase, and uploads the updates of the submodel without revealing the submodel index or the values of the updates in the writing phase. In this work, we first provide a basic communication efficient PRUW scheme, and study further means of reducing the communication cost via sparsification. Gradient sparsification is a widely used concept in learning applications, where only a selected set of parameters is downloaded and updated, which significantly reduces the communication cost. In this paper, we study how the concept of sparsification can be incorporated in private FSL with the goal of reducing the communication cost, while guaranteeing information-theoretic privacy of the updated submodel index as well as the values of the updates. To this end, we introduce two schemes: PRUW with top $r$ sparsification and PRUW with random sparsification. The former communicates only the most significant parameters/updates among the servers and the users, while the latter communicates a randomly selected set of parameters/updates. The two proposed schemes introduce novel techniques such as parameter/update (noisy) permutations to handle the additional sources of information leakage in PRUW caused by sparsification. Both schemes result in significantly reduced communication costs compared to that of the basic (non-sparse) PRUW scheme.

Logarithmic Sobolev inequalities are a fundamental class of inequalities that play an important role in information theory. They play a key role in establishing concentration inequalities and in obtaining quantitative estimates on the convergence to equilibrium of Markov processes. More recently, deep links have been established between logarithmic Sobolev inequalities and strong data processing inequalities. In this paper we study logarithmic Sobolev inequalities from a computational point of view. We describe a hierarchy of semidefinite programming relaxations which give certified lower bounds on the logarithmic Sobolev constant of a finite Markov operator, and we prove that the optimal values of these semidefinite programs converge to the logarithmic Sobolev constant. Numerical experiments show that these relaxations are often very close to the true constant even for low levels of the hierarchy. Finally, we exploit our relaxation to obtain a sum-of-squares proof that the logarithmic Sobolev constant is equal to half the Poincaré constant for the specific case of a simple random walk on the odd $n$ -cycle, with $n\in \{5,7, {\dots },21\}$ . Previously this was known only for $n=5$ and even $n$ .

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most $t$ deletions in non-binary sequences. When the alphabet size $q$ is even, we first propose a non-binary code correcting a burst of at most 2 deletions for $q$ -ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most $t$ where $t$ is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.

Motivated by the recent application of two-dimensional Golay complementary arrays (2-D GCA) in uniform rectangular array (URA) -based omnidirectional precoding for the next generation of cellular communications, we propose in this paper new constructions of GCA pairs and GCA quads, which allow for more possible sizes. These constructions are facilitated by four identities over a commutative ring, of which two are established results of quaternions and octonions and the others are novel. We prove that the size of a 4-phase GCA pair is possible if the product of the array sizes in all dimensions is a 4-phase Golay number with an additional constraint on the factorization of the product. For 2-phase 2-D GCA quads, all sizes no greater than $78\times 78$ can be covered. For 4-phase GCA quads, all the positive integers within 1000 can be covered for the size in one dimension. Besides producing GCAs that can accommodate to antenna arrays of various sizes, this study also yields new Hadamard matrices of sizes previously unavailable.

Sequences with a low correlation have very important applications in communications, cryptography, and compressed sensing. In the literature, many efforts have been made to construct good sequences with various lengths, where binary sequences attract great attention. As a result, various constructions of good binary sequences have been proposed. However, most of the known constructions made use of the multiplicative cyclic group structure of finite field $\mathbb {F}_{p^{n}}$ for a prime $p$ and a positive integer $n$ . In fact, all $p^{n}+1$ rational places including the place at infinity of the rational function field over $\mathbb {F}_{p^{n}}$ can form a cyclic structure under an automorphism of order $p^{n}+1$ . In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length $p^{n}+1$ via cyclotomic function fields over $\mathbb {F}_{p^{n}}$ for any odd prime $p$ . Each family of binary sequences has size $p^{n}-2$ and its correlation is upper bounded by $4+\lfloor 2\cdot p^{n/2}\rfloor $ . To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length $p^{n}+1$ for odd prime $p$ . Moreover, our sequences can be constructed explicitly and have competitive parameters.

Classical quickest change detection algorithms require modeling pre-change and post-change distributions. Such an approach may not be feasible for various machine learning models because of the complexity of computing the explicit distributions. Additionally, these methods may suffer from a lack of robustness to model mismatch and noise. This paper develops a new variant of the classical Cumulative Sum (CUSUM) algorithm for the quickest change detection. This variant is based on Fisher divergence and the Hyvärinen score and is called the Hyvärinen score-based CUSUM (SCUSUM) algorithm. The SCUSUM algorithm allows the applications of change detection for unnormalized statistical models, i.e., models for which the probability density function contains an unknown normalization constant. The asymptotic optimality of the proposed algorithm is investigated by deriving expressions for average detection delay and the mean running time to a false alarm. Numerical results are provided to demonstrate the performance of the proposed algorithm.

This paper proposes a novel shift-sum decoding method for non-binary cyclic codes, which only requires finite field operations but yields advanced decoding performance. Using the cyclically different minimum-weight dual codewords (MWDCs) and their proper shifts, a frequency matrix can be obtained as a reliability metric for identifying the error positions and magnitudes. By analyzing the statistical distributions of the matrix entries, the rationale for the shift-sum decoding’s advanced error-correction capability is revealed. Based on this decoding method, a hard-decision iterative shift-sum (HISS) decoding algorithm is first proposed. It can correct errors beyond half of the code’s minimum Hamming distance. By further utilizing the reliability information obtained from the channel, a soft-decision iterative shift-sum (SISS) decoding algorithm is then proposed to improve the decoding performance. Both the HISS and the SISS algorithms are realized only with polynomial multiplications and numerical comparisons, which are hardware-friendly. To further improve the error-correction performance, the HISS and SISS algorithms can be integrated in a Chase decoding mechanism for handling the test-vectors. Simulation results on Reed-Solomon (RS) and non-binary BCH (NB-BCH) codes show that the proposed algorithms yield a competent decoding and complexity performances in comparison with the existing decoding algorithms.

It is important to study constructions of plateaued functions with balancedness and high algebraic degrees for preventing cryptographic attacks. Our goal of this paper is to find practical construction methods for producing infinite families of balanced $r$ -plateaued functions with maximal algebraic degrees for every positive integer $r$ . We first present a theoretical framework for secondary constructions of plateaued functions. From this framework, we derive three practical algorithms by controlling initial input vectors. These algorithms produce $(s+1)$ -plateaued functions from a given bent function and $s$ -plateaued functions in a recursive way for any nonnegative integer $s$ ; therefore, we obtain $r$ -plateaued functions for every $r > s$ . Then we obtain three concrete construction methods of balanced $r$ -plateaued functions with maximal algebraic degrees from the algorithms. For implementation, in the tables, we list up some initial bent (0-plateaued) functions, which guarantee the maximality of algebraic degrees of plateaued functions. Furthermore, we discuss the complexities of the three algorithms, which shows the feasibility of our methods. We emphasize that this is the first time to give constructions of balanced $r$ -plateaued functions with maximal algebraic degrees for every positive integer $r$ as far as we know.

Magnetic recording devices are still competitive in the storage density race with solid-state devices thanks to new technologies such as two-dimensional magnetic recording (TDMR). TDMR offers remarkable storage density increase without the need for new magnetic materials; however, advanced data processing schemes are needed to guarantee reliability. Data patterns where a bit is surrounded by complementary bits at the four positions with Manhattan distance 1 on the TDMR grid are called plus isolation (PIS) patterns, and they are error-prone. Recently, we introduced lexicographically-ordered constrained (LOCO) codes, namely optimal plus LOCO (OP-LOCO) codes, with minimal redundancy that prevent these patterns from being written in a TDMR device. However, in the high-density regime or the low-energy regime (as the device ages), additional error-prone patterns emerge, specifically data patterns where a bit is surrounded by complementary bits at only three positions with Manhattan distance 1, and we call them incomplete plus isolation (IPIS) patterns. In this paper, we present capacity-achieving codes that forbid both PIS and IPIS patterns in TDMR systems with wide read heads. Because of their shape, we collectively call the PIS and IPIS patterns rotated T isolation (RTIS) patterns, and we call the new codes optimal T LOCO (OT-LOCO) codes. We analyze OT-LOCO codes and derive their simple encoding-decoding rule that allows reconfigurability. We also present a novel bridging idea for these codes to further increase the rate. Our simulation results demonstrate that OT-LOCO codes not only remarkably outperform OP-LOCO codes, but also entirely eliminate media noise effects, resulting from error-prone data patterns, at practical TD densities in the range [0.6, 0.8) with high rates in the range [0.81, 0.83]. At the TD density of 0.8, the OT-LOCO code of rate 0.8267 achieves a frame error rate (bit error rate) performance gain of about 1.15 orders (1.23 orders) of magnitude for all TDMR down (horizontal) tracks compared with the uncoded setting. To further preserve the storage capacity, we suggest using OP-LOCO codes, which have higher rates than OT-LOCO codes, early in the device lifetime, then employing the reconfiguration property to switch to OT-LOCO codes later in the device lifetime. While the point of reconfiguration on the density/energy axis is decided manually at the moment, the next step is to use machine learning to make that decision based on the TDMR device status. Moreover, we introduce another coding scheme to remove RTIS patterns in TDMR systems which offers lower complexity, lower error propagation, and track separation, at the expense of a limited rate loss.

Recently, simplicial complexes are used in constructions of several infinite families of minimal and optimal linear codes by Hyun et al. Building upon their research, in this paper more linear codes over the ring $\mathbb {Z}_{4}$ are constructed by simplicial complexes. Specifically, the Lee weight distributions of the resulting quaternary codes are determined and two infinite families of four-Lee-weight quaternary codes are obtained. Compared to the databases of $\mathbb Z_{4}$ codes by Aydin et al., at least nine new quaternary codes are found. Thanks to the special structure of the defining sets, we have the ability to determine whether the Gray images of certain obtained quaternary codes are linear or not. This allows us to obtain two infinite families of binary nonlinear codes and one infinite family of binary minimal linear codes. Furthermore, utilizing these minimal binary codes, some secret sharing schemes as a byproduct also are established.

Self-orthogonal codes have nice applications in many areas including quantum codes, lattices and LCD codes. For a prime power $q$ , it is in general difficult to construct $q$ -ary self-orthogonal codes. In the literature, there exists no simple method to judge whether a general $q$ -ary linear code is self-orthogonal or not. In this paper, we mainly present several families of $q$ -ary self-orthogonal codes and study their applications in quantum codes and LCD codes. Firstly, several families of $q$ -ary linear codes are constructed by some special defining sets. These codes are proved to be self-orthogonal. To this end, we determine the numbers of solutions of some systems of equations over finite fields. Secondly, three families of $q$ -ary quantum codes with unbounded length and minimum distance three are constructed from the self-orthogonal codes. These quantum codes are optimal according to the quantum Hamming bound. In particular, some of them have better parameters than known ones. Thirdly, several families of $q$ -ary LCD codes are constructed from the self-orthogonal codes. Many optimal or almost optimal binary and ternary LCD codes are produced by our constructions. Some binary and ternary LCD codes have better parameters than known ones.

Doeblin coefficients are a classical tool for analyzing the ergodicity and exponential convergence rates of Markov chains. Propelled by recent works on contraction coefficients of strong data processing inequalities, we investigate whether Doeblin coefficients also exhibit some of the notable properties of canonical contraction coefficients. In this paper, we present several new structural and geometric properties of Doeblin coefficients. Specifically, we show that Doeblin coefficients form a multi-way divergence, exhibit tensorization, and possess an extremal trace characterization. We then show that they also have extremal coupling and simultaneously maximal coupling characterizations. By leveraging these characterizations, we demonstrate that Doeblin coefficients act as a nice generalization of the well-known total variation (TV) distance to a multi-way divergence, enabling us to measure the “distance” between multiple distributions rather than just two. We then prove that Doeblin coefficients exhibit contraction properties over Bayesian networks similar to other canonical contraction coefficients. We additionally derive some other results and discuss an application of Doeblin coefficients to distribution fusion. Finally, in a complementary vein, we introduce and discuss three new quantities: max-Doeblin coefficient, max-DeGroot distance, and min-DeGroot distance. The max-Doeblin coefficient shares a connection with the concept of maximal leakage in information security; we explore its properties and provide a coupling characterization. On the other hand, the max-DeGroot and min-DeGroot measures extend the concept of DeGroot distance to multiple distributions.

Gold functions are well-known for designing sequences with good correlation properties. This paper reveals a fascinating relationship between Gold functions and Golay-Davis-Jedwab (GDJ) Boolean functions to design sequences with low correlation and low PAPR, which is the first of its kind. The bent and semi-bent properties of the Gold functions are utilized to derive the correlation of the resultant binary spreading sequence sets, while the complementary properties of the GDJ Boolean functions are used to derive the low PAPR. Based on this idea we propose three new sets of binary spreading sequences with low PAPR and low correlation. The proposed sequence sets have the potential to be used as spreading sequences in non-orthogonal multiple access (NOMA). They have a very large set size, which in turn results in a high overloading factor as compared to the existing sequence sets with the same length and the same correlation, which are generated through systematic constructions.