Search

This paper considers the problem of constructing a confidence sequence, which is a sequence of confidence intervals that hold uniformly over time, for estimating the mean of bounded real-valued random processes. This paper revisits the gambling-based approach established in the recent literature from a natural two-horse race perspective, and demonstrates new properties of the resulting algorithm induced by Cover (1991)’s universal portfolio. The main result of this paper is a new algorithm based on a mixture of lower bounds, which closely approximates the performance of Cover’s universal portfolio with constant per-round time complexity. A higher-order generalization of a lower bound on a logarithmic function in (Fan et al., 2015), which is developed as a key technique for the proposed algorithm, may be of independent interest.

This paper considers the secure aggregation problem for federated learning under an information theoretic cryptographic formulation, where distributed training nodes (referred to as users) train models based on their own local data and a curious-but-honest server aggregates the trained models without retrieving other information about users’ local data. Secure aggregation generally contains two phases, namely key sharing phase and model aggregation phase. Due to the common effect of user dropouts in federated learning, the model aggregation phase should contain two rounds, where in the first round the users transmit masked models and, in the second round, according to the identity of surviving users after the first round, these surviving users transmit some further messages to help the server decrypt the sum of users’ trained models. The objective of the considered information theoretic formulation is to characterize the capacity region of the communication rates from the users to the server in the two rounds of the model aggregation phase, assuming that key sharing has already been performed offline in prior. In this context, Zhao and Sun completely characterized the capacity region under the assumption that the keys can be arbitrary random variables. More recently, an additional constraint, known as “uncoded groupwise keys,” has been introduced. This constraint entails the presence of multiple independent keys within the system, with each key being shared by precisely $\mathsf S$ users, where $\mathsf S$ is a defined system parameter. The capacity region for the information theoretic secure aggregation problem with uncoded groupwise keys was established in our recent work subject to the condition ${\mathsf S}\gt {\mathsf K}-{\mathsf U}$ , where $\mathsf K$ is the number of total users and $\mathsf U$ is the designed minimum number of surviving users (which is another system parameter). In this paper we fully characterize the capacity region for this problem by matching a new converse bound and an achievable scheme. Experimental results over the Tencent Cloud show the improvement on the model aggregation time compared to the original secure aggregation scheme.

In the classical “Bits Through Queues” paper, it was hypothesized that full feedback always increases the capacity of first-in-first-out queues, except when the service time distribution is memoryless. More recently, a non-explicit sufficient condition under which feedback increases capacity was provided, along with simple examples of service times meeting this condition. While this condition yields examples where feedback is beneficial, it does not offer explicit structural properties of such service times. In this paper, we show that full feedback increases capacity whenever the service time has bounded support. This is achieved by investigating a generalized notion of feedback, with full feedback and weak feedback as particular cases.

Private information retrieval (PIR) codes and batch codes are two important types of codes that are designed for coded distributed storage systems and private information retrieval protocols. These codes have been the focus of much attention in recent years, as they enable efficient and secure storage and retrieval of data in distributed systems. In this paper, we introduce a new class of codes called $(s,t)$ -batch codes. These codes are a type of storage codes that can handle any multi-set of t requests, comprised of s distinct information symbols. Importantly, PIR codes and batch codes are special cases of $(s,t)$ -batch codes. The main goal of this paper is to explore the relationship between the number of redundancy symbols and the $(s,t)$ -batch code property. Specifically, we establish a lower bound on the number of redundancy symbols required and present several constructions of $(s,t)$ -batch codes. Furthermore, we extend this property to the case where each request is a linear combination of information symbols, which we refer to as functional $(s,t)$ -batch codes.

In this paper, we generalize the log-Sobolev inequalities to Rényi–Sobolev inequalities by replacing the entropy with the two-parameter entropy, which is a generalized version of entropy and closely related to Rényi divergences. We derive the sharp nonlinear dimension-free version of this kind of inequalities. Interestingly, the resultant inequalities show a transition phenomenon depending on the parameters. We then connect Rényi–Sobolev inequalities to contractive and data-processing inequalities, concentration inequalities, and spectral graph theory. Our proofs in this paper are based on the information-theoretic characterization of the Rényi–Sobolev inequalities, as well as the method of types.

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server. The “secure” nature of such aggregation consists of the fact that no information about the local users’ data must be leaked to the server except the aggregated local models. In order to guarantee security, some keys may be shared among the users (this is referred to as the key sharing phase). After the key sharing phase, each user masks its trained model which is then sent to the server (this is referred to as the model aggregation phase). This paper follows the information theoretic secure aggregation problem originally formulated by Zhao and Sun, with the objective to characterize the minimum communication cost from the $\mathsf K$ users in the model aggregation phase. Due to user dropouts, which are common in real systems, the server may not receive all messages from the users. A secure aggregation scheme should tolerate the dropouts of at most ${\mathsf K}-{\mathsf U}$ users, where $\mathsf U$ is a system parameter. The optimal communication cost is characterized by Zhao and Sun, but with the assumption that the keys stored by the users could be any random variables with arbitrary dependency. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of applications besides federated learning, in this paper we add one constraint into the above problem, namely, that the key variables are mutually independent and each key is shared by a group of $\mathsf S$ users, where $\mathsf S$ is another system parameter. To the best of our knowledge, all existing secure aggregation schemes (with information theoretic security or computational security) assign coded keys to the users. We show that if ${\mathsf S}\gt {\mathsf K}-{\mathsf U}$ , a new secure aggregation scheme with uncoded groupwise keys can achieve the same optimal communication cost as the best scheme with coded keys; if ${\mathsf S}\leq {\mathsf K}-{\mathsf U}$ , uncoded groupwise key sharing is strictly sub-optimal. Finally, we also implement our proposed secure aggregation scheme into Amazon EC2, which are then compared with the existing secure aggregation schemes with offline key sharing.

Distributed Source Coding (DSC), a scheme that encodes multiple correlated sources separately while decoding their bitstreams jointly, is an important branch of network information theory. Due to the advantages of shifting complexity burden from the encoder to the decoder and canceling the flow of data across terminals, DSC has potential applications in many scenarios, e.g., wireless sensor network, distributed genome data compression, etc. There are two forms (lossless and lossy) of DSC. Overlapped arithmetic codes, featured by overlapped intervals, are a variant of arithmetic codes that can implement distributed lossless compression, or the so-called Slepian-Wolf coding. For uniform binary sources, an overlapped arithmetic code is essentially a nonlinear many-to-one mapping that partitions source space into unequal-sized cosets. To analyze overlapped arithmetic codes, two theoretical tools have been proposed, i.e., Coset Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS). The former describes how source space is partitioned into cosets (equally or unequally), and the latter describes how codewords are structured within each coset (densely or sparsely). However, until now, these two tools are almost parallel to each other, and it seems that there is no intersection between them. The main contribution of this paper is tightly bridging HDS with CCS. Specifically, HDS can be quickly and accurately calculated with CCS in some cases. In addition, the paper also proves the necessary and sufficient condition for the convergence of HDS and reveals the close relation between divergent HDS and polynomial division. All theoretical analyses are verified by experimental results.

This paper introduces a construction of quantum CSS codes from a tuple of component CSS codes and two collections of subsets. The resulting codes have parallelizable encoding and syndrome measurement circuits and built-in redundancy in the syndrome measurements. In a certain subfamily of the general construction, the resulting codes are related to a natural generalization of classical Reed-Muller codes, and this leads to formulas for the distance of the quantum code as well as for the distance of the associated classical code that protects against errors in the syndrome. The paper gives a number of examples of codes with block size $2^{m}, m=3, {\dots },9$ , and with syndrome measurements involving 2, 4 or 8 qubits. These include codes for which the distance exceeds the syndrome measurement weight, as well as codes which provide asymmetric protection against bit flip and phase flip errors.

In this paper, we derive variational formulas for the asymptotic exponents (i.e., convergence rates) of the concentration and isoperimetric functions in the product Polish probability space under certain mild assumptions. These formulas are expressed in terms of relative entropies (which are from information theory) and optimal transport cost functionals (which are from optimal transport theory). Hence, our results verify an intimate connection among information theory, optimal transport, and concentration of measure or isoperimetric inequalities. In the concentration regime, the corresponding variational formula is in fact a dimension-free bound in the sense that this bound is valid for any dimension. A cardinality bound for the alphabet of the auxiliary random variable in the expression of the asymptotic isoperimetric exponent is provided, which makes the expression computable by a finite-dimensional program for the finite alphabet case. We lastly apply our results to obtain an isoperimetric inequality in the classic isoperimetric setting, which is asymptotically sharp under certain conditions. The proofs in this paper are based on information-theoretic and optimal transport techniques.

This paper addresses the problem of generating a common random string with min-entropy k using an unlimited supply of quantum isotropic states, with minimal communication between Alice and Bob. Quantum isotropic states can be seen as maximally entangled states polluted by a depolarizing channel. The paper considers two communication models – one-way classical communication and one-way quantum communication, and derives upper bounds on the optimal common randomness rates for both models. We show that in the case of classical communication, quantum isotropic states have no advantage over noisy classical correlation. In the case of quantum communication, we demonstrate that the common randomness rate can be increased by using superdense coding on quantum isotropic states. We also prove an upper bound on the optimal common randomness rate achievable by using one-way quantum communication. As an application, our result yields an upper bound on the classical capacity of the noiseless quantum channel assisted by quantum isotropic states.

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.

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 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.

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

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.

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.

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 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.

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.

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$ .

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.

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.

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.

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.

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.

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.

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.

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.

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.

Spectral clustering has been widely used for community detection in network sciences. While its empirical successes are well-documented, a clear theoretical understanding, particularly for sparse networks where degrees are much smaller than $\log n$ , remains unclear. In this paper, we address this significant gap by demonstrating that spectral clustering offers exponentially small error rates when applied to sparse networks under Stochastic Block Models. Our analysis provides sharp characterizations of its performance, backed by matching upper and lower bounds possessing an identical exponent with the same leading constant. The key to our results is a novel truncated $\ell _{2}$ perturbation analysis for eigenvectors, coupled with a new analysis idea of eigenvectors truncation.

In this paper, we investigate the problem of deciding whether two random databases $\textsf {X}\in {\mathcal { X}} ^{n\times d}$ and $\textsf {Y}\in {\mathcal { Y}} ^{n\times d}$ are statistically dependent or not. This is formulated as a hypothesis testing problem, where under the null hypothesis, these two databases are statistically independent, while under the alternative, there exists an unknown row permutation $\sigma $ , such that $\textsf {X}$ and $\textsf {Y}^{\sigma } $ , a permuted version of $\textsf {Y}$ , are statistically dependent with some known joint distribution, but have the same marginal distributions as the null. We characterize the thresholds at which optimal testing is information-theoretically impossible and possible, as a function of n, d, and some spectral properties of the generative distributions of the datasets. For example, we prove that if a certain function of the eigenvalues of the likelihood function and d, is below a certain threshold, as $d\to \infty $ , then weak detection (performing slightly better than random guessing) is statistically impossible, no matter what the value of n is. This mimics the performance of an efficient test that thresholds a centered version of the log-likelihood function of the observed matrices. We also analyze the case where d is fixed, for which we derive strong (vanishing error) and weak detection lower and upper bounds.

An edit refers to a single insertion, deletion, or substitution. This paper aims to construct binary codes that can correct two edits. To do this, a necessary and sufficient condition for a code to be two-edit correctable is provided, showing that a code is a two-edit correcting code if and only if it can correct two deletions, up to two substitutions, and one deletion and up to one substitution, separately. This criterion allows for the construction of two-edit correcting codes leveraging these three types of error correcting codes. In the field of constructing codes for correcting two deletions, we present a construction with $4\log n+O(\log \log n)$ redundant bits that can be viewed as a subcode proposed by Guruswami and Håstad, and provide an alternative proof. Moreover, our two-deletion correcting codes can also correct up to two substitutions after making a slight modification. In the field of constructing codes for correcting one deletion and up to one substitution, we present a construction with $4 \log n+O(\log \log n)$ redundant bits, which outperforms the best previously known results $6 \log n+O(1)$ . Leveraging these codes, we obtain a construction of two-edit correcting codes with $6 \log n+O(\log \log n)$ redundant bits. This outperforms the best previously known result, which requires at least $8\log n$ redundant bits. Moreover, we also consider the list-decoding problem under the two-edit channel and construct a two-edit list-decodable code with a list size of two employing $4 \log n+O(\log \log n)$ redundant bits.

The class of $\ell $ -maximum distance separable ( $\ell $ -MDS) codes is a generalization of maximum distance separable (MDS) codes that has attracted a lot of attention due to its applications in several areas such as secret sharing schemes, index coding problems, informed source coding problems and combinatorial t-designs. In this paper, for $\ell =1$ , we completely solve a conjecture recently proposed by Heng et al. (Discrete Mathematics, 346 (10): 113538, 2023) and obtain infinite families of 1-MDS codes with general dimensions holding 2-designs. These later codes are also proved to be optimal locally recoverable codes. For general positive integers $\ell $ and $\ell '$ , we construct new $\ell $ -MDS codes from known $\ell '$ -MDS codes via some classical propagation rules involving the extended, expurgated, and $({\mathbf {u}},{\mathbf {u}}+{\mathbf {v}})$ constructions. Finally, we study some general results including characterization, weight distributions, and bounds on maximum lengths of $\ell $ -MDS codes, which generalize, simplify, or improve some known results in the literature.

An $(n, k, d; r)_{q}$ -locally repairable code (LRC) is called a Singleton-optimal LRC if it achieves the Singleton-type bound. Analogous to the classical MDS conjecture, the maximal length problem of Singleton-optimal LRCs has attracted a lot of attention in recent years. In this paper, we give an improved upper bound for the length of q-ary Singleton-optimal LRCs with disjoint repair groups such that $(r+1)\mid n$ based on the parity-check matrix approach. In particular, for any Singleton-optimal $(n, k, d; r)_{q}$ -LRCs, we show that: 1) $n\le q+d-4$ , when $r=2$ and $d=3e+8$ with $e\ge 0$ ; 2) $n\leq (r+1)\left \lfloor {{\frac {2(q^{2}+q+1)}{r(r+1)} +e+1}}\right \rfloor $ , when $d\ge 8$ and $\max \left \{{{3,\frac {d-e-6}{e+1}}}\right \}\le r\le \frac {d-e-3}{e+1}$ for any $0\le e\le \left \lfloor {{\frac {d-6}{4} }}\right \rfloor $ . Furthermore, we establish equivalent connections between the existence of Singleton-optimal $(n,k,d;r)_{q}$ -LRCs for $d=6, r=3$ and $d=7, r=2$ with disjoint repair groups and some subsets of lines in finite projective space with certain properties. Consequently, we prove that the length of q-ary Singleton-optimal LRCs with minimum distance $d=6$ and locality $r=3$ is upper bounded by $O(q^{1.5})$ . We construct Singleton-optimal $(8\le n\le q+1,k,d=6,r=3)_{q}$ -LRC with disjoint repair groups such that $4\mid n$ and determine the exact value of the maximum code length for some specific q. We also prove the existence of $(n, k, d=7; r=2)_{q}$ -Singleton-optimal LRCs for $n \approx \sqrt {2}q$ .

In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple “types” of items. Specifically, we assume that there are multiple disjoint semi-defective sets, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as Concomitant Group Testing (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (namely, 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).

This paper considers the Gaussian multiple access wiretap channel (GMAC-WT) with selfish transmitters, i.e., who are each solely interested in maximizing their individual secrecy rate. The question then arises as to whether selfish transmitters can increase their individual secrecy rate by participating in a collective, i.e, multiple access, protocol instead of operating on their own. If yes, the question arises whether there is a protocol that satisfies all the participating transmitters simultaneously, in the sense that no transmitter has an incentive to deviate from the protocol. Utilizing coalitional game theory, these questions are addressed for the degraded GMAC-WT with an arbitrary number of transmitters and for the non-degraded GMAC-WT with two transmitters. In particular, for the degraded GMAC-WT, cooperation is shown to be in the best interest of all transmitters, and the existence of protocols that incentivize all transmitters to participate is established. Furthermore, a unique, fair, stable, and achievable secrecy rate allocation is determined. For the non-degraded GMAC-WT, depending on the channel parameters, there are cases where cooperation is not in the best interest of all transmitters, and cases where it is. In the latter cases, a unique, fair, stable, and achievable secrecy rate allocation is determined.

Fourier phase retrieval (PR) is a severely ill-posed inverse problem that arises in various applications. To guarantee a unique solution and relieve the dependence on the initialization, background information can be exploited as a structural prior. However, the requirement for the background information may be challenging when moving to high-resolution imaging. At the same time, the previously proposed projected gradient descent (PGD) method also demands much background information. In this paper, we present an improved theoretical result about the demand for the background information, along with two Douglas Rachford (DR) based methods. Analytically, we demonstrate that the background information required to ensure a unique solution can be decreased by nearly $1/2$ for the 2-D signals compared to the 1-D signals. By generalizing the results into d-dimension, we show that the length of the background information more than $\left ({{2^{\frac {d+1}{d}}-1}}\right)$ folds of the signal is sufficient to ensure uniqueness. At the same time, we also analyze the stability and robustness of the model when the measurements and background information are corrupted by noise. Furthermore, two methods called Background Douglas Rachford (BDR) and Convex Background Douglas Rachford (CBDR) are proposed. BDR, which is a kind of non-convex method, is proven to have the local R-linear convergence rate under mild assumptions. Instead, the CBDR method uses the techniques of convexification and can be proven to have a global convergence guarantee as long as the background information is sufficient. To support this, a new property called F-RIP is established. We test the performance of the proposed methods through simulations as well as real experimental measurements, and demonstrate that they achieve a higher recovery rate with less background information compared to the PGD method.

The identification of changes in linear models is a fundamental problem encountered in various applications. Traditional methods often encounter difficulties when attempting to identify changepoints in the presence of heavy-tailed distribution. This paper focuses on the study of high-dimensional linear models with multiple structural changes in the presence of heavy-tailed errors, especially for those errors without moment conditions. We first propose a robust method that simultaneously estimates regression coefficient and changepoint by incorporating $\ell _{1}$ norm penalized Wilcoxon rank loss minimization for single changepoint estimation. Furthermore, we extend it to multiple changepoints estimation based on a novel two-step moving window mechanism that combines fast coarse grid screening and an efficient refinement. Our method exhibits robustness against heavy-tailed random errors while maintaining high efficiency for normal random errors. Theoretically, we establish non-asymptotic error bounds with a near-oracle rate for the estimates of both the coefficient and the changepoint under weak conditions on the random error distribution. Numerical results provide evidence for the validity and effectiveness of the proposed approach.

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek et al., (2023). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by $\rm {MDS}(\ell)$ where $\ell $ denotes the order of generality, $\rm {MDS}(2)$ codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an ${[}n,k{]}$ - $\rm {MDS}(\ell)$ codes is $\Omega _{\ell } (n^{\ell -1})$ , whereas the best known (non-explicit) upper bound is $O_{\ell } (n^{k(\ell -1)})$ which is exponential in the dimension. In this work, we nearly close this exponential gap between upper and lower bounds. We show that an ${[}n,k{]}$ - $\rm {MDS}(3)$ codes requires a field of size $\Omega _{k}(n^{k-1})$ , which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question by Shangguan and Tamo, (2020). We also give explicit constructions of ${[}n,k{]}$ - $\rm {MDS}(\ell)$ code over fields of size $n^{(\ell k)^{O(\ell k)}}$ . The smallest non-trivial case where we still do not have optimal constructions is ${[}n,3{]}$ - $\rm {MDS}(3)$ . In this case, the known lower bound on the field size is $\Omega (n^{2})$ and the best known upper bounds are $O(n^{5})$ for a non-explicit construction and $O(n^{32})$ for an explicit construction. In this paper, we give an explicit construction over fields of size $O(n^{3})$ which comes very close to being optimal.

Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.

In this paper, we present new families of quantum channels for which corresponding minimum output Rényi p-entropy is not additive. Our manuscript is motivated by the results of Grudka et al. and we focus on channels characterized by both extensions and subspaces of the antisymmetric subspace in $\mathbb {C}^{d} \otimes \mathbb {C} ^{d}$ , which exhibit additivity breaking for $p\gt 2$ .