Search

This paper starts by considering the minimization of the Rényi divergence subject to a constraint on the total variation distance. Based on the solution of this optimization problem, the exact locus of the points \bigl ( D(Q\|P1), D(Q\|P2) \bigr ) is determined when P1 , P2 , and $Q$ are arbitrary probability measures which are mutually absolutely continuous, and the total variation distance between P1 and P2 is not below a given value. It is further shown that all the points of this convex region are attained by probability measures which are defined on a binary alphabet. This characterization yields a geometric interpretation of the minimal Chernoff information subject to a constraint on the variational distance. This paper also derives an exponential upper bound on the performance of binary linear block codes (or code ensembles) under maximum-likelihood decoding. Its derivation relies on the Gallager bounding technique, and it reproduces the Shulman–Feder bound as a special case. The bound is expressed in terms of the Rényi divergence from the normalized distance spectrum of the code (or the average distance spectrum of the ensemble) to the binomially distributed distance spectrum of the capacity-achieving ensemble of random block codes. This exponential bound provides a quantitative measure of the degradation in performance of binary linear block codes (or code ensembles) as a function of the deviation of their distance spectra from the binomial distribution. An efficient use of this bound is considered. [ABSTRACT FROM PUBLISHER]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. In this paper, we concentrate on testing the hypothesis $H_0$ : the number of defectives $\leq s_1$ against the alternative hypothesis $H_1$ : the number of defectives $\geq s_2$. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on $s_1$ and $s_2$ , the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates interplay among storage overhead, bandwidth requirement, and security constraint in distributed storage. In the model used in our analysis, storage nodes are dispersed in multiple clusters. When a node fails, necessary content gets restored by downloading data from different nodes that may possibly be in other clusters. The bandwidth required for transferring data for node repair is assumed more scarce for cluster-to-cluster links than the links connecting intra-cluster nodes. Eavesdropping takes place on links across clusters only, and a fraction of the total number of clusters is assumed compromised. When a cluster is compromised, any repair traffic going in and out of it is eavesdropped. For this clustered model with eavesdroppers, we analyze the security of distributed storage systems (DSSs) and provide guidelines on designing system solutions for securing the data. First, under the setting of functional repair, we derive a general upper bound on the secrecy capacity, the maximum data size that can be stored in DSSs with perfect secrecy. In the practically important bandwidth-limited regime where the node storage size is equal to the repair bandwidth, the upper bound is shown to be achievable through proposed code constructions. Moreover, we obtain a closed-form expression for the required system resources-node storage size and repair bandwidth-to store a given amount of data with perfect secrecy. Second, we investigate the behavior of secrecy capacity as the number of compromised clusters increases. According to our mathematical analysis, the secrecy capacity decreases as a quadratic function until the number of compromised clusters reaches a certain threshold. Finally, based on the fundamental relationship between the system resources and the secrecy capacity, we provide a guideline on balancing intra- and cross-cluster repair bandwidths depending on the given system security level. [ABSTRACT FROM AUTHOR]

Precoding-aided spatial modulation (PSM) is a multi-antenna communication scheme, which jointly modulates information bits into both the spatial index and the signaling constellation. Specifically, the spatial bits are conveyed by the index of a receive antenna, which is steered at by precoding at the transmitter. In this paper, the indices of the receive antennas are called a spatial constellation in contrast to the signaling constellation. We investigate the symbol error rate (SER) of the PSM scheme to strike a fine tradeoff between the signaling and the spatial constellation, i.e., the signaling-spatial constellation tradeoff, which minimizes the system's SER. First, we formulate the SER of the PSM scheme. Then, an explicit upper bound on the SER is determined based on an approximation using a weighted sum of exponentials. By minimizing the SER upper bound, we show that for phase-shift keying modulation, it achieves a sufficiently good tradeoff when the size of the signaling constellation is 4, i.e., the quadrature phase-shift keying. The numerical results show that the signaling-spatial constellation tradeoff determined by the derived SER upper bound significantly outperforms other PSM schemes with equal spectral efficiency. [ABSTRACT FROM AUTHOR]

At CRYPTO 2017 and IEEE Transactions on Computers in 2018, Todo et al. proposed the division property based cube attack method making it possible to launch cube attacks with cubes of dimensions far beyond practical reach. However, assumptions are made to validate their attacks. In this paper, we further formulate the algebraic properties of the superpoly in one framework to facilitate cube attacks in more successful applications: we propose the "flag" technique to enhance the precision of MILP models, which enable us to identify proper non-cube IV assignments; a degree evaluation algorithm is presented to upper bound the degree of the superpoly s.t. the superpoly can be recovered without constructing its whole truth table and overall complexity of the attack can be largely reduced; we provide a divide-and-conquer strategy to Trivium-like stream ciphers namely Trivium, Kreyvium, TriviA-SC1/2 so that the large scale MILP models can be split into several small solvable ones enabling us to analyze Trivium-like primitives with more than 1000 initialization rounds; finally, we provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. We apply our techniques to attack the initialization of several ciphers namely 839-round Trivium, 891-round Kreyvium, 1009-round TriviA-SC1, 1004-round TriviA-SC2, 184-round Grain-128a and 750-round Acorn respectively. [ABSTRACT FROM AUTHOR]

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and nonsmooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA (W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Trans. Signal Process., vol. 63, no. 22, pp. 6013–6023, 2015), but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Second, for the special case without nonsmooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries. [ABSTRACT FROM AUTHOR]

In 2007, Carlet and Ding introduced two parameters, denoted by $Nb_{F}$ and $NB_{F}$ , quantifying respectively the balancedness of general functions $F$ between finite Abelian groups and the (global) balancedness of their derivatives $D_{a} F(x)=F(x+a)-F(x)$ , $a\in G\setminus \{0\}$ (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided inequalities relating the nonlinearity $\mathcal {NL}(F)$ to $NB_{F}$ for S-box and specifically obtained an upper bound on the nonlinearity that unifies Sidelnikov-Chabaud-Vaudenay’s bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions $F+L$ , where $L$ is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario et al. for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives, respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without comparing the second pair of parameters to the first one. In this paper, we observe that ambiguity is the same parameter as $NB_{F}$ up to additive and multiplicative constants (i.e., up to rescaling). We perform the necessary work of comparison and unification of the results on $NB_{F}$ and on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any finite Abelian groups. More importantly, we derive many new results on these parameters. [ABSTRACT FROM AUTHOR]

This paper investigates the throughput for wireless network with full-duplex radios using stochastic geometry. Full-duplex (FD) radios can exchange data simultaneously with each other. On the other hand, the downside of FD transmission is that it will inevitably cause extra interference to the network compared to half-duplex (HD) transmission. Moreover, the residual self-interference has negative effects on the network throughput. In this paper, we focus on a wireless network of nodes with both HD and FD capabilities and derive and optimize the throughput in such a network. Our analytical result shows that if the network is adopting an ALOHA protocol, the maximal throughput is achieved by scheduling all concurrently transmitting nodes to work in either FD mode or HD mode depending on one simple condition. Moreover, the effects of imperfect self-interference cancellation on the signal-to-interference ratio (SIR) loss and throughput are also analyzed based on our mathematical model. We rigorously quantify the impact of imperfect self-interference cancellation on the throughput gain, transmission range, and other metrics, and we establish the minimum amount of self-interference suppression needed for FD to be beneficial. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a novel concatenated coding scheme for enabling error resilience in two distributed storage settings: one being storage using existing regenerating codes and the second being storage using locally repairable codes. The concatenated coding scheme brings together a maximum rank distance code as an outer code and either a globally regenerating or a locally repairable code as an inner code. In addition, error resilience for combination of locally repairable codes with regenerating codes is considered. This concatenated coding system is designed to handle two different types of adversarial errors: the first type includes an adversary that can replace the content of an affected node only once; while the second type studies an adversary that is capable of polluting data an unbounded number of times. The paper establishes an upper bound on the resilience capacity for a locally repairable code. This paper also proves that the proposed concatenated coding approach attains the upper bound on the resilience capacity in the presence of the first type of adversary for both minimum storage regenerating codes and locally repairable codes. Further, this paper presents mechanisms that combine the presented concatenated coding scheme with subspace signatures to achieve error resilience for the second type of errors. [ABSTRACT FROM PUBLISHER]

In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness. [ABSTRACT FROM AUTHOR]

A distributed storage system (DSS) is one of the most vital components of a cloud computing system used for storing and sharing big data among authorized users. A typical DSS consists of ${ n}$ storage nodes each with a storage capacity of ${\alpha }$ units of data such that the entire file stored on the DSS can be recovered by accessing any ${k < n}$ nodes. The objective of this paper is to construct fractional repetition (FR) codes with applications in DSSs. FR codes are the key to constructing a class of distributed storage codes with exact repair by transfer (i.e., upon failure, a failed storage node is exactly regenerated through simple downloading). A major drawback of existing FR codes is that they are insufficiently flexible to adapt adequately to system changes in DSSs. To address this problem, this paper introduces a new type of FR codes, called pliable FR codes, in which both the per-node storage ${\alpha }$ and repetition degree ${ \rho }$ can easily and simultaneously be adjusted. In addition, this paper presents several constructions of pliable FR codes and provides a relatively comprehensive analysis of the constructed pliable FR codes, which reveals the following versatile properties of the codes: 1) the transposed codes of the constructed codes are also pliable FR codes; 2) the constructed codes attain a tight upper bound on the file size with equality at least for ${1 \le k < \min (3, k' + 1)}$ , where ${k'}$ is the smallest value of ${k}$ such that ${k \alpha - (k - 1) > \frac {n - 1}{\rho - 1}}$ ; 3) the constructed codes also meet a Singleton-like bound on the minimum distance at least for ${1 \le k < 3}$ , which demonstrates their optimality; 4) the computational complexity necessary for determining the file size or the minimum distance of the constructed codes can be greatly reduced when it is hard to exactly determine them; and 5) the constructed codes can be used as fractional repetition batch codes to provide load balancing in DSSs, for which the batch size (i.e., the number of symbols that can be read in parallel) can be exactly determined. [ABSTRACT FROM AUTHOR]

A nonlinear feedback shift register (NFSR) of $n$ -stage is called irreducible if, the family of output sequences of any NFSR of stage less than $n$ is not included in that of the NFSR. Tian and Qi in this paper [IEEE-IT, 2013(6),4006–4012] gave a lower bound on the density of irreducible NFSRs. In this paper, we improve their lower bound and also give an upper bound on the density of irreducible NFSRs. Moreover, the gap between our upper and lower bounds is less than 0.04. [ABSTRACT FROM PUBLISHER]

In this correspondence paper, we provide a new look at the boundedness problems of error covariance of Kalman filtering. First, by utilizing the mathematical induction technique, a new bound function which is dependent on system parameters is proposed. In this manner, the boundedness problems of the error covariance can be converted to the study of the corresponding uniform bounds of the bound function. Second, based on such a bound function, the dynamic behaviors, monotonicities, and boundedness problems of error covariance are deeply explored. Consequently, a few quantitative results under minimal conditions about the uniform bounds on error covariance are obtained. Finally, examples are given to verify the correctness and effectiveness of our theoretical analyses. [ABSTRACT FROM AUTHOR]

This paper considers a Gaussian channel with one transmitter and two receivers. The goal is to maximize the communication rate at the intended/primary receiver subject to a disturbance constraint at the unintended/secondary receiver. The disturbance is measured in terms of the minimum mean square error (MMSE) of the interference that the transmission to the primary receiver inflicts on the secondary receiver. This paper presents a new upper bound for the problem of maximizing the mutual information subject to an MMSE constraint. The new bound holds for vector inputs of any length and recovers a previously known limiting (when the length of the vector input tends to infinity) expression from the work of Bustin et al. The key technical novelty is a new upper bound on the MMSE. This bound allows one to bound the MMSE for all signal-to-noise ratio (SNR) values below a certain SNR at which the MMSE is known (which corresponds to the disturbance constraint). The bound also complements the “single-crossing point property” of the MMSE that upper bounds the MMSE for all SNR values above a certain value at which the MMSE value is known. The MMSE upper bound provides a refined characterization of the phase-transition phenomenon, which manifests, in the limit as the length of the vector input goes to infinity, as a discontinuity of the MMSE for the problem at hand. For vector inputs of size n=1 , a matching lower bound, to within an additive gap of order O ( \log \log ({1}/{\sf MMSE}) ) (where {\sf MMSE}$ is the disturbance constraint), is shown by means of the mixed inputs technique recently introduced by Dytso et al. [ABSTRACT FROM PUBLISHER]

Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, C0 , of a noisy channel. This is defined as the least upper bound of rates, at which, it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length $n=1,2,\ldots$ , in contrast to the long lengths required for the known regular capacity achieving codes, such as turbo codes, LDPC codes, and polar codes. Both wrap around and non-wrap around limited magnitude error models are considered in this paper. For non-wrap around error model, the exact value of zero error capacities is derived, and optimal non-systematic and systematic codes are designed. The non-systematic codes achieve the zero error capacity with any finite length. The optimal systematic codes achieve the systematic zero error capacity of the channel, which is defined as the zero error capacity with the additional requirements that the communication must be carried out with a systematic code. It is also shown that the rates of the proposed systematic codes are equal to or approximately equal to the zero error capacity of the channel. For the wrap around model bounds are derived for the zero error capacity and in many cases the bounds give the exact value. In addition, optimal wrap around non-systematic and systematic codes are developed which either achieve or are close to achieving the zero error capacity with finite length. [ABSTRACT FROM PUBLISHER]

Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no $[[27, 15, 5]]$ or $[[28, 14, 6]]$ stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved. [ABSTRACT FROM PUBLISHER]

In range analysis (RA), suitable integer bit-widths are assigned to the variables so that no overflow occurs. Although the accuracy in RA rather than error analysis has more impact on hardware cost and efficiency, there are few works that offer new approaches to improve RA. Arithmetic functions, mostly represented by polynomials, are normally suitable for both optimization and verification purposes. In this paper, a safe and more accurate RA of feed-forward fixed-point polynomial data-flow graphs is proposed. The method employs particular features of RA and maps it to a specific class of polynomial optimization problems. The proposed method provides tighter ranges while taking less runtime in comparison with satisfiability-modulo theory-based method. Furthermore, the improved ranges lead to enhance the area and delay efficiency more than 50% and 24%, respectively, when the circuits are implementing the functions in comparison with the state-of-the-art techniques. [ABSTRACT FROM PUBLISHER]

This paper studies the fundamental tradeoff between storage and latency in a general wireless interference network with caches equipped at all transmitters and receivers. The tradeoff is characterized by an information-theoretic metric, normalized delivery time (NDT), which is the worst case delivery time of the actual traffic load at a transmission rate specified by degrees of freedom of a given channel. We obtain both an achievable upper bound and a theoretical lower bound of the minimum NDT for any number of transmitters, any number of receivers, and any feasible cache size tuple. We show that the achievable NDT is exactly optimal in certain cache size regions, and is within a bounded multiplicative gap to the theoretical lower bound in other regions. In the achievability analysis, we first propose a novel cooperative transmitter/receiver coded caching strategy. It offers the freedom to adjust file splitting ratios for NDT minimization. We then propose a delivery strategy that transforms the considered interference network into a new class of cooperative X-multicast channels. It leverages local caching gain, coded multicasting gain, and transmitter cooperation gain (via interference alignment and interference neutralization) opportunistically. Finally, the achievable NDT is obtained by solving a linear programming problem. This paper reveals that with caching at both transmitter and receiver sides, the network can benefit simultaneously from traffic load reduction and transmission rate enhancement, thereby effectively reducing the content delivery latency. [ABSTRACT FROM PUBLISHER]

We study the channel capacity of a general discrete energy harvesting channel with a finite battery. Contrary to traditional communication systems, the transmitter of such a channel is powered by a device that harvests energy from a random exogenous energy source and has a finite-sized battery. As a consequence, at each transmission opportunity, the system can only transmit a symbol whose energy is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is simultaneously random, instantaneous, and influenced by the full history of the inputs and the energy harvesting process. Furthermore, naturally, in such a channel, the energy information is observed causally at the transmitter. Both of these characteristics pose great challenges for the analysis of the channel capacity. In this paper, we use techniques developed for channels with side information and finite-state channels, to obtain lower and upper bounds on the capacity of energy harvesting channels. In particular, in a general case with Markov energy harvesting processes, we use stationarity and ergodicity theory to compute and optimize the achievable rates for the channels, and derive a series of computable capacity upper and lower bounds. [ABSTRACT FROM AUTHOR]

Depletion and deforestation of forest resources are mainly due to industrialization, population, pollution, forest fire, improper commercial logging, and illegal logging in the world. In this paper, we consider two dynamic models. A mathematical Model 1 is proposed considering the forest biomass density x(t), the density of wood‐based industries y(t) with unknown parameter h. Model 2 is an extension of Model 1 with the density of illegal logging z(t) with unknown parameter n. It is assumed that the density of forest biomass grows logistically in the absence of wood‐based industries and illegal logging. In the proposed models, the controlling parameters h and n are crucial parameters for the local stable conditions of the equilibrium points and system control. We also show in this paper that it is possible to control illegal logging by increasing the level of logging by selecting system parameters efficiently and effectively. Recommendations for Resource ManagersDepletion and deforestation of Mongolian forest resource are mainly due to forest fire, illegal logging. We consider mathematical models of forest depletion due to forest operation and illegal logging.Mongolian forest's current situation is that the rate of illegal logging is higher than the wood‐based industries. We show that this situation can be changed by changing the parameters.Based on the mathematical modeling and statistical analysis, we define the upper bound of the rate of resources of the wood‐based industries.We also presented that it is possible to control the parameters efficiently. The result suggests that to approximate the limit of wood utilized for the nationwide supply from the government it is necessary to increase the current amount of forest utility considering the actual forest resources and demands. [ABSTRACT FROM AUTHOR]

In this paper we improve the upper bound of the third order Hankel determinant for the class of Ozaki close-to-convex functions. The sharp bound is conjectured. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

The Maximum Clique Problem (MCP) is a classic NP-hard problem, which has the goal of finding the largest possible clique. It is known to have direct applications in a wide spectrum of fields such as data association problems appearing in bioinformatics and computational biology, computer vision and robotics. Solutions like using brute force, backtracking and branch and bound are designed to deal with the maximum problem. In the branch and bound method, a branch is pruned if the currently found largest clique is better than its upper bound. However, the upper bound obtained by current methods is often not close enough to the ω (G) , leading to large inefficient search space. This paper discusses the branch and bound procedure to solve the maximum clique problem in large and sparse graphs and proposes a new efficient branch and bound maximum clique algorithm named SMC-BRB. SMC-BRB solves the maximum clique problem in heuristic search stage and exact search stage. It simultaneously utilizes the s + -index and color-based upper bound in heuristic search stage, which effectively reduces the number of branches in the exact search stage. This method is beneficial to the solution of MCP because it provides a scale reduction on heuristic search stage. Experimental results show that SMC-BRB has better performance than the state-of-the-art algorithm MC-BRB, which demonstrates the efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

The yield criterion of many metallic materials differs from the von Mises yield criterion. However, the available upper bound solutions are almost all restricted to this criterion. The objective of the present paper was to derive an upper bound solution based on a generalized yield criterion for evaluating the extrusion and drawing force, assuming a conical die. The solution method differs from the conventional method used in conjunction with the von Mises yield criterion. The development of this method is necessary, since the work function is not readily expressed as an explicit function of strain rate invariants if the generalized yield criterion is adopted. The solution is illustrated using numerical examples, which show the effect of the yield criterion on the limit load. [ABSTRACT FROM AUTHOR]

Radio antennas switch signals in the form of radio waves using different frequency bands of the electromagnetic spectrum. To avoid interruption, each radio station is assigned a unique number. The channel assignment problem refers to this application. A radio geometric mean labeling of a connected graph G is an injective function h from the vertex set, V (G) to the set of natural numbers N such that for any two distinct vertices x and y of G , h (x) · h (y) ≥ d i a m + 1 − d (x , y) . The radio geometric mean number of h , r g m n (h) , is the maximum number assigned to any vertex of G. The radio geometric mean number of G, r g m n (G) is the minimum value of r g m n (h) , taken over all radio geometric mean labeling h of G . In this paper, we present two theorems for calculating the exact radio geometric mean number of paths and cycles. We also present a novel algorithm for determining the upper bound for the radio geometric mean number of a given graph. We verify that the upper bounds obtained from this algorithm coincide with the exact value of the radio geometric mean number for paths, cycles, stars, and bi-stars. [ABSTRACT FROM AUTHOR]

Due to the advantage of capacity-achieving, polar codes have been extended to the block fading channel whereas most constructions involve complex iterative-calculation. In this paper, we establish a systematic framework to analyze the error performance of polar codes in the case of block mapping and random mapping. For both the mappings, by introducing the new concept, named split polar spectrum, we derive the upper bound on the error probability of polarized channel which explicitly reveals the relationship between the diversity order $L$ and the block-wise weight distribution of the codeword. For the special case $L=2$ in the block mapping, we design the enumeration algorithm to calculate the exact split polar spectrum based on the general MacWilliams identities. For arbitrary diversity order in the random mapping, with the help of uniform interleaving, we derive the approximate split polar spectrum by combining the polar spectrum and the probability of fading pattern for a specific weight. Furthermore, we propose the design criteria to construct polar codes over the block fading channel. The full diversity criterion is the primary target to achieve the diversity gain and the product distance criterion requires to maximize the product of the block-wise Hamming distance whereby obtain the coding gain. Guided by these design criteria, the construction metrics, respectively named polarized diversity weight (PDW) and simplified PDW (SPDW) are proposed to designpolar codes in both mappings. Such simple metrics can construct polar codes with similar or better performance over those based on traditional methods in block fading channel. [ABSTRACT FROM AUTHOR]

Multiple-input-multiple-output (MIMO) systems significantly increase the network throughput and coverage probability for short-packet communications. In this paper, a tight lower bound on the average achievable rate of MIMO short-packet communication systems is theoretically derived, considering flat uncorrelated Rayleigh fading MIMO channels. The derivations are based on the eigenvalue analysis of a Wishart matrix and Jensen's inequality. Given the actual transmission rate, a tight approximation on the average block error rate (BLER) of MIMO short-packet communication systems is also provided, which is based on the moment generating function and inverse Laplace transform. Numerical results demonstrate that both our theoretically derived analytical average achievable rate lower bound and approximate average BLER are almost the same as the simulation results. [ABSTRACT FROM AUTHOR]

The notion of correlation immune functions has been introduced by Siegenthaler (1984) in symmetric cryptography in the framework of stream ciphers. At the conference CRYPTO’91 by Camion et al., it has been pointed out that this notion existed in statistics and combinatorics. It has recently been highlighted that such functions also play an important role in a new framework related to side-channel attack counter-measures. Since then, the interest in correlation immune Boolean functions has been renewed, and new challenges regarding these functions have appeared. Specifically, low Hamming weight correlation immune functions have been selected as useful for counter-measures to side-channel attacks. Despite their importance, the literature is not abundant in this research direction. Two very interesting articles in which such correlation immune functions were nicely explored, given this novel use of them. Carlet initiated the first one in 2013, and the second one is due to Carlet and Chen (2018). This paper deals with correlation immune Boolean functions aiming to produce more candidates of those processing low Hamming weights. We shall focus on correlation immune Boolean functions with Hamming weights power of 2 (which offer a flexibility to control the correlation immunity aspects) and present several methods of designing them. Some design methods are efficient and could be employed to derive such functions. Consequently, given two positive integers $n$ and $m$ , we derive new effective constructions of correlation immune Boolean functions with Hamming weight power of 2. Furthermore, an upper bound on the correlation immunity of the newly constructed $n$ -variable Boolean functions with Hamming weight $2^{m}$ was determined for $n-m\ge 0$. Besides, exact values and lower bounds on the maximum correlation immunity of those functions are explored and discussed, mainly when the values of $n$ and $m$ are very close. This paper also exhibits explicit examples of those correlation immune functions that illustrate our methods. [ABSTRACT FROM AUTHOR]

In this paper, a novel training beam sequence design for multiuser millimeter wave tracking systems is proposed. For each receiver, a single-path channel model is firstly investigated, where we introduce a maximum a posteriori (MAP) criterion to estimate the time-varying angle of departure (AoD), followed by an extended Kalman filter to update the stale complex path gain. We then employ training beam sequence design to minimize the estimated AoD’s average mean squared error (AMSE), which however has no explicit expression. We firstly derive a closed-form upper bound for the AMSE and then simplify this upper bound into a tractable form, based on which a nonlinear optimization problem (NLP) is formulated. By solving this NLP optimally using its corresponding Karush-Kuhn-Tucker conditions, we obtain an efficient training beam sequence. The proposed MAP criterion and its associated training beam sequence design are further extended to multi-path scenarios, where a joint estimation of the multiple paths is firstly discussed, followed by a sequential estimation as a low-complexity alternative. Numerical results demonstrate the superiority of our proposed scheme over the existing benchmark methods, especially in the case when the receivers’ channels change rapidly. [ABSTRACT FROM AUTHOR]

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

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

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

In this paper, a predefined time sliding mode control with prescribed performance is presented for dual-inertia driving systems with unknown disturbances. A modified prescribed performance function (PPF) without requiring the accurate initial error is designed to guarantee that the tracking error remains within the prescribed boundary. An adaptive law is then constructed to estimate the unknown upper boundary parameters of the lumped dynamics (e.g., parameter uncertainties and external disturbances), so that the prior knowledge of the upper bound of uncertainties is not required. The parameter estimation is incorporated into the control design to eliminate the effects of the unknown dynamics. Using the sliding mode technique, an adaptive predefined time sliding mode control is developed. The proposed control method can achieve fast convergence rate of the tracking error, and the stability of the closed-loop system is proved via the Lyapunov function method. Comparative experiments are carried out based on a dual-inertia driving system to validate the efficacy of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters $R$ and $E$ are guaranteed to achieve a rate $R$ and an error exponent $E$ . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed. [ABSTRACT FROM AUTHOR]

In practice, sequences with long period but lightweight generation are always welcome in the applications of communication systems; however, the generation is not easy. From a certain angle of very high probability, this paper presents a solution, which is performed using cyclic difference sequences. As an application, the generated sequences can be interleaved to obtain good correlation properties. Furthermore, synchronization with blind detection is often required but difficult to be achieved. Even harder, periodic sequences may be affected to be ultimately periodic sequences with overhead because of device switching or noise. The determinations of the ultimate periods of above sequences and corresponding distributions are also investigated in this paper. [ABSTRACT FROM PUBLISHER]

This paper presents an optimization approach for a system consisting of multiple bidirectional links over a two-way amplify-and-forward relay. Improvement to the fairness of the system is desired. All user pairs exchange information over one relay station (RS) with multiple antennas. Due to the joint transmission to all users, the users are subject to mutual interference. A mitigation of the interference can be achieved by max–min fair precoding optimization where the relay is subject to a sum power constraint. The resulting optimization problem is nonconvex. This paper proposes a novel iterative low-complexity approach based on a modified Levenberg–Marquardt (LM) method to find near optimal solutions. The presented method finds solutions close to the standard convex-solver-based relaxation approach. [ABSTRACT FROM PUBLISHER]

This paper focuses on the problem of broadcasting information in the most efficient manner in a large 2-D ad hoc wireless network at low SNR and under line-of-sight propagation. A new communication scheme is proposed, where source nodes first broadcast their data to the entire network, despite the lack of sufficient available power. The signal’s power is then reinforced via successive back-and-forth beamforming transmissions between different groups of nodes in the network, so that all nodes are able to decode the transmitted information at the end. This scheme is shown to achieve asymptotically the broadcast capacity of the network, which is expressed in terms of the largest singular value of the matrix of fading coefficients between the nodes in the network. A detailed mathematical analysis is then presented to evaluate the asymptotic behavior of this largest singular value. [ABSTRACT FROM PUBLISHER]

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance. [ABSTRACT FROM PUBLISHER]

Determining a single-letter secrecy-capacity formula for the arbitrarily varying wiretap channel (AVWTC) is an open problem largely because of two main challenges. Not only does it capture the difficulty of the compound wiretap channel (another open problem), it also requires that secrecy is ensured with respect to exponentially many possible channel state sequences. By extending the strong soft-covering lemma, recently derived by the authors, to the heterogeneous scenario, this paper accounts for the exponential number of secrecy constraints while only imposing single-letter constraints on the communication rate. Through this approach, we derive a single-letter characterization of the correlated-random (CR)-assisted semantic-security (SS) capacity of an AVWTC with a type constraint on the allowed state sequences. The allowed state sequences are the ones in a typical set around a single constraining type. The stringent SS requirement is established by showing that the mutual information between the message and the eavesdropper’s observations is negligible even when maximized over all message distributions, choices of state sequences, and realizations of the CR-code. Both the achievability and the converse proofs of the type-constrained coding theorem rely on stronger claims than actually required. The direct part establishes a novel single-letter lower bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained by any convex and closed set of state probability mass functions. This bound achieves the best known single-letter secrecy rates for a corresponding compound wiretap channel over the same constraint set. In contrast to other single-letter results in the AVWTC literature, this paper does not assume the existence of a best channel to the eavesdropper. Instead, SS follows by leveraging the heterogeneous version of the strong soft-covering lemma and a CR-code reduction argument. Optimality is a consequence of a max-inf upper bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained to any collection of type-classes. When adjusted to the aforementioned compound WTC, the upper bound simplifies to a max–min structure, thus strengthening the previously best known single-letter upper bound by Liang et al. that has a min–max form. The proof of the upper bound uses a novel distribution coupling argument. The capacity formula shows that the legitimate users effectively see an averaged main channel, while security must be ensured versus an eavesdropper with perfect channel state information. An example visualizes our single-letter results, and their relation to the past multi-letter secrecy-capacity characterization of the AVWTC is highlighted. [ABSTRACT FROM PUBLISHER]

In this paper, the source estimation problem is investigated in a wireless sensor network (WSN) with energy-harvesting (EH) nodes. We first consider a deterministic EH model where the amount of harvested energy at each node is known prior to transmissions. For such a model, we investigate the average mean-square-error (MSE) minimization problem over a finite horizon of multiple estimation periods and derive the optimal solution. Moreover, a more realistic stochastic EH model is considered, where only the current amount of harvested energy is known. The corresponding MSE minimization problem over an infinite horizon is formulated. The Lyapunov optimization technique is adopted to obtain a solution for the stochastic EH problem. Simulation results are conducted to validate the effectiveness of the proposed solutions for both the deterministic and stochastic EH models. [ABSTRACT FROM AUTHOR]

This paper presents a polar coding scheme to achieve secrecy in block fading binary symmetric wiretap channels without the knowledge of instantaneous channel state information (CSI) at the transmitter. For this model, a coding scheme that hierarchically utilizes polar codes is presented. In particular, on the polarization of different binary symmetric channels over different fading blocks, each channel use is modeled as an appropriate binary erasure channel over fading blocks. Polar codes are constructed for both coding over channel uses for each fading block and coding over fading blocks for certain channel uses. In order to guarantee security, random bits are introduced at appropriate places to exhaust the observations of the eavesdropper. It is shown that this coding scheme, without instantaneous CSI at the transmitter, is secrecy capacity achieving for the simultaneous fading scenario. For the independent fading case, the capacity is achieved when the fading realizations for the eavesdropper channel are always degraded with respect to the receiver. For the remaining cases, the gap between lower and upper bounds is analyzed. Remarkably, for the scenarios where the secrecy capacity is achieved, the results imply that the instantaneous CSI does not increase the secrecy capacity. [ABSTRACT FROM PUBLISHER]

In this paper, we consider an intelligent reflecting surface (IRS) enabled mobile network, where a fixed access point (AP) communicates with a mobile user (MU) via the aid of an IRS. We assume that the MU moves from one elementary square to another following a Markov random walk within a grid, and propose a maximum a posteriori (MAP) criterion to track the movement of the MU by leveraging the line-of-sight component of the IRS-MU link. Since it is infeasible to derive an explicit expression for the average probability of estimation error (APEE) for the proposed MAP criterion, we derive a closed-form upper bound for the APEE, which is used as the cost function to optimize the phase shifts of the IRS units. Considering the unit modulus constraints incurred by the IRS units, a manifold optimization (MO) method is firstly employed to gain a favorable solution to the formulated optimization problem, followed by a low-complexity codebook based solution to circumvent the high computational cost of the MO method. Our numerical results demonstrate the superior performance of the proposed IRS phase shift designs over the benchmark method. [ABSTRACT FROM AUTHOR]

This paper proposes a fractional-order sliding mode controller (FOSMC) for fixed-time stability of multimachine power systems. Fractional calculus has been applied in sliding mode control (SMC) to design FOSMC which can better suppress the chattering phenomenon than the traditional integer-order SMC. Hence, a FOSMC is proposed to regulate the excitation of synchronous generators to improve the transient stability of the power system. In addition, the FOSMC can maintain the multimachine power systems stabilization in an upper bound and measurable convergence time independent of the initial operating conditions of the power system. The Lyapunov function is implemented to demonstrate the stability of multimachine power systems under the FOSMC, and the upper bound convergence time of the power system is generally estimated. The New England 10-machine 39-bus power system is taken into simulation to test the effectiveness and superior performances of the FOSMC than the existing control methods under different operating conditions. Meanwhile, the FOSMC with different orders are presented to verify that the FOSMC can better restrain the chattering phenomenon than traditional integer-order SMC. Simulation results show that the FOSMC can effectively reduce the chattering phenomenon and ensure the power system stabilization in an upper bound time, thus enhancing the dynamic performances of the power system. [ABSTRACT FROM AUTHOR]

Recently, maximum correntropy criterion (MCC) has been widely and successfully used in robust signal processing and machine learning, in which the correntropy is maximized instead of minimizing the popular mean square error (MSE) to improve the robustness with respect to outliers or impulsive noises. A lot of efforts have been devoted to derive different adaptive algorithms under MCC, but to date, little insight has been gained as to how the MCC solution will be influenced by outliers. In this paper, we investigate this problem and our focus is mainly on the parameter estimation of a simple linear errors-in-variables (EIVs) model with scalar variables. Under some conditions, we derive an upper bound on the absolute value of the estimation error and show that the MCC solution can get very close to the true value of the unknown parameter even with arbitrarily large outliers in both the input and output variables. Illustrative examples are provided to verify and clarify the theory. [ABSTRACT FROM AUTHOR]

In this paper, a cooperative spatial modulation (SM) based non-orthogonal multiple access (NOMA) scheme with simultaneous wireless information and power transfer is proposed. In particular, NOMA is applied at the base station (BS) and the near user (U1) acts as an energy harvesting full-duplex relay to assist the far user (U2). The data bits of U1 and U2 are mapped into SM symbols and amplitude/phase modulation symbols, respectively. Furthermore, the rate of U1 is maximized while satisfying the target rate of U2 by jointly designing the power allocation coefficient, power-splitting ratio, and transmit power of U1. To solve the non-convex problem, a successive convex approximation-based iterative algorithm is developed. Finally, numerical results reveal that the proposed scheme can achieve the superior performance compared to existing schemes. [ABSTRACT FROM AUTHOR]

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