Search

In this paper, we present a generic construction of r -ary sequences with period p q 2 based on the Euler quotient modulo p q , where p and q are odd primes satisfying that p divides q − 1 and r is any prime less than q. The minimal polynomial and the linear complexity of the proposed sequences are determined in most cases under the assumption that r q − 1 ≢ 1   (mod   q 2). The result shows that each of the sequences has large linear complexity. [ABSTRACT FROM AUTHOR]

Kim, Chung, No and Chung introduced new families of M-ary sequences by using Sidel'nikov sequences and the shift-and-add method. Chung, No and Chung constructed more families of M-ary sequences based on Sidel'nikov sequences and the shift-and-inverse method. In this paper we further study the balancedness of these sequences and show that they have asymptotical uniform pattern distributions under some assumptions on the parameters of the sequences. Linear complexity profiles of the sequences are also studied. [ABSTRACT FROM AUTHOR]

Linear complexity is an important pseudo-random measure of the key stream sequence in a stream cipher system. The 1-error linear complexity is used to measure the stability of the linear complexity, which means the minimal linear complexity of the new sequence by changing one bit of the original key stream sequence. This paper contributes to calculating the exact values of the linear complexity and 1-error linear complexity of the binary key stream sequence with two prime periods defined by Ding–Helleseth generalized cyclotomy. We provide a novel method to solve such problems by employing the discrete Fourier transform and the M–S polynomial of the sequence. Our results show that, by choosing appropriate parameters p and q, the linear complexity and 1-error linear complexity can be no less than half period, which shows that the linear complexity of this sequence not only meets the requirements of cryptography but also has good stability. [ABSTRACT FROM AUTHOR]

Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. The self-attention mechanism underpinning the strength of ViTs has a quadratic complexity in both computation and memory usage. This motivates the development of approximating the self-attention at linear complexity. However, an in-depth analysis in this work reveals that existing methods are either theoretically flawed or empirically ineffective for visual recognition. We identify that their limitations are rooted in the inheritance of softmax based self-attention during approximations, that is, normalizing the scaled dot-product between token feature vectors using the softmax function. As preserving the softmax operation challenges any subsequent linearization efforts. By this insight, a family of SOftmax-Free Transformers (SOFT) are proposed. Specifically, a Gaussian kernel function is adopted to replace the dot-product similarity, enabling a full self-attention matrix to be approximated under low-rank matrix decomposition. For computational robustness, we estimate the Moore–Penrose inverse using an iterative Newton–Raphson method in the forward process only, while calculating its theoretical gradients only once in the backward process. To further expand applicability (e.g., dense prediction tasks), an efficient symmetric normalization technique is introduced. Extensive experiments on ImageNet, COCO and ADE20K show that our SOFT significantly improves the computational efficiency of existing ViT variants. With linear complexity, much longer token sequences are permitted by SOFT, resulting in superior trade-off between accuracy and complexity. Code and models are available at https://github.com/fudan-zvg/SOFT. [ABSTRACT FROM AUTHOR]

Two classes of optimal quaternary sequences have been constructed by applying the sign alternation transform and Gray mapping to Legendre sequence pair, twin-prime sequence pair and GMW sequence pair. In this paper, a new method for investigating the linear complexity over finite field is proposed, and the exact values of the linear complexity over finite field F 4 and Galois ring Z 4 of the quaternary sequences are determined. The results show that their linear complexity are quite good. [ABSTRACT FROM AUTHOR]

Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements on the topic of complexity measures for randomness assessment, which are of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences, and their relations with Lempel–Ziv complexity, expansion complexity, 2-adic complexity and correlation measures. [ABSTRACT FROM AUTHOR]

The linear complexity of new generalized cyclotomic sequences with odd period was estimated. The sequences were defined using generalized cyclotomic classes composite modulo. Conditions sufficient for the existence of binary and non-binary sequences with high linear complexity were obtained. The earlier results on the linear complexity of sequences with the period equal to the power of a prime were generalized.

Linear complexity is an important pseudo-random measure of the keystream sequence in a stream cipher system. The error linear complexity is employed to measure the stability of the linear complexity, which means the minimal linear complexity by changing few bit of the original keystream sequence. This paper contributes to calculating the linear complexity of a famous generalized cyclotomic sequences of period pq defined by Ding and Helleseth. We give the linear complexity of these sequences in a new way, and calculate further the 1-error linear complexity of them. The result shows that the sequences have good stability in terms of linear complexity.

Recently, the transformer-based model e.g., the vision transformer (ViT) has been extensively used in computer vision tasks. The superior performance of the ViT leads to the requirement of an enormous dataset and the complexity of calculating self-attention between patches is quadratic in nature. To acknowledge these two concerns, this paper proposes a novel shifted patch tokenization swin transformer (SPT-Swin) for the image classification task. The shifted patch tokenization (SPT) compensates for the data deficiency by increasing the data samples based on spatial information of the image patches while the swin transformer provides linear computational complexity by calculating self-attention between the shifted window based patches. For model validation, the SPT-Swin framework is trained on popular benchmark image datasets such as ImageNet-1K, CIFAR-10 and CIFAR-100, and the classification accuracies are found 89.45%, 95.67% and 92.95% respectively. Moreover, the comparative analysis of the proposed model with the existing state-of-the-art models shows that the classification performances are improved by 7.05%, 4.14%, and 8.30% for the ImageNet-1K, CIFAR-10 and CIFAR-100 datasets respectively. Therefore, our proposed SPT-based data augmentation technique with the core swin transformer model could be a data-efficient linear complex-able model for future computer vision tasks.

Boolean functions are crucial primitive in block cipher and are also used to design pseudorandom sequences. They play a crucial role in the design of symmetric cryptography and its analysis, and the study on the cryptographic properties of Boolean functions is a hotspot in cryptography. The hidden weighted bit functions (HWBF) are paid attention since they have many “good” cryptographic measures. However, there are no results on their linear complexity in the literature. Therefore, this paper discusses a family of binary sequences of period [2n]built by using [n-]variable HWBF (hidden weighted bit functions). It is proven that such sequences are balanced with maximal linear complexity using mathematical method. The 2-error linear complexity of the sequences is also determined in terms of the Hasse derivative and Lucas congruence. When [n(mod4)∈{0,1,3}], the values of the 2-error linear complexity are maximal. Results indicate that such sequences are of “good” cryptographic measures.

Let p = e f + 1 be an odd prime, where e ≡ 0 (mod 4) . A family of balanced quaternary sequences is defined by using the classical cyclotomic classes of order e with respect to p in this paper. We derive the formulas for their linear complexity and trace representation over Z 4 by computing the discrete Fourier transform of these sequences. As an application, the linear complexity and trace representation over Z 4 are given for two types of specific sequences with low autocorrelation derived from the cyclotomic classes of order 4 and 8, respectively. Furthermore, we also determine the exact linear complexity and minimal polynomial for each sequence of the second type over the finite field F 4 . [ABSTRACT FROM AUTHOR]

The detection of community structures is a very crucial research area. The problem of community detection has received considerable attention from a large portion of the scientific community. More importantly, these articles are spread across a large number of different disciplines, from computer science, to statistics, and social sciences. The analysis of modern social networks becomes rather cumbersome, as their size and number keeps growing larger and larger. Moreover, in the modern communities, users participate in large number of groups. From the network perspective, efficient methods should be developed to automatically identify overlapping communities, that is, communities with overlapping nodes. In this work, we use a probabilistic network model to characterize and identify linked communities with common nodes. The innovative idea in this work is that the communities are represented as Markovian networks with continuously changing states. Each state represents the number of users within a cluster, that have specific characteristic classes. Based on the current state, we introduce a fast, linear on the number of newly added users, approach to estimate the probability of each cluster to be homogeneous in terms of sets of user characteristics and to determine how well the new user fit within a community. Because of the linear computations involved, our proposed probabilistic model can detect communities and overlaps with low execution time and high accuracy, as shown in our experimental results. The experimental results have shown that our probabilistic scheme executes faster and provides more robust communities compared to competitive schemes.

Several reasonably cyclotomic sequences are constructed by cyclotomic classes having good pseudo-randomness property. In this paper, we derive the linear complexity of an extended binary cyclotomic sequences of order 2 l t over finite field having period p q. Our result shows that these sequences have higher linear complexity, which can resist linear attack. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Frontiers of Computer Science & Technology is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Considering the spectral properties of images, we propose a new self-attention mechanism with highly reduced computational complexity, up to a linear rate. To better preserve edges while promoting similarity within objects, we propose individualized processes over different frequency bands. In particular, we study a case where the process is merely over low-frequency components. By ablation study, we show that low frequency self-attention can achieve very close or better performance relative to full frequency even without retraining the network. Accordingly, we design and embed novel plug-and-play modules to the head of a CNN network that we refer to as FsaNet. The frequency self-attention 1) requires only a few low frequency coefficients as input, 2) can be mathematically equivalent to spatial domain self-attention with linear structures, 3) simplifies token mapping ($1\times 1$ convolution) stage and token mixing stage simultaneously. We show that frequency self-attention requires 87.29% ~ 90.04% less memory, 96.13% ~ 98.07% less FLOPs, and 97.56% ~ 98.18% in run time than the regular self-attention. Compared to other ResNet101-based self-attention networks, FsaNet achieves a new state-of-the-art result (83.0% mIoU) on Cityscape test dataset and competitive results on ADE20k and VOCaug. FsaNet can also enhance MASK R-CNN for instance segmentation on COCO. In addition, utilizing the proposed module, Segformer can be boosted on a series of models with different scales, and Segformer-B5 can be improved even without retraining. Code is accessible at https://github.com/zfy-csu/FsaNet. [ABSTRACT FROM AUTHOR]

Finding a provably correct subquadratic synchronization algorithm for many filesystem replicas is one of the main theoretical problems in operational transformation (OT) and conflict-free replicated data types (CRDT) frameworks. Based on the algebraic theory of filesystems, which incorporates non-commutative filesystem commands natively, we developed and built a proof-of-concept implementation of an algorithm suite which synchronizes an arbitrary number of replicas. The result is provably correct, and the synchronized system is created in linear space and time after an initial sorting phase. It works by identifying conflicting command pairs and requesting one of the commands to be removed. The method can be guided to reach any of the theoretically possible synchronized states. The algorithm also allows asynchronous usage. After the client sends a synchronization request, the local replica remains available for further modifications. When the synchronization instructions arrive, they can be merged with the changes made since the synchronization request. The suite also works on filesystems with a directed acyclic graph-based path structure in place of the traditional tree-like arrangement. Consequently, our algorithms apply to filesystems with hard or soft links as long as the links create no loops. [ABSTRACT FROM AUTHOR]

In this paper, a new class of generalized cyclotomic binary sequences with period $ 4p^n $ is proposed. These sequences are almost balanced, and the explicit formulas of their linear complexity and autocorrelation are presented. [ABSTRACT FROM AUTHOR]

For the binary sequences of period N, when their nonlinear complexity is N -- 1 or N -- 2, the number of these sequences with the same linear complexity and nonlinear complexity is determined. When their nonlinear complexity is N -- 3, the relation among the number of sequences with different linear complexity is given. For arbitrary periodic binary sequences with the same linear complexity and nonlinear complexity, an upper bound of the number of their different minimal polynomials is obtained. [ABSTRACT FROM AUTHOR]

Quaternary sequences with high linear complexity and N-adic complexity have been widespread concerned in cryptography. By using the Gray mapping, we construct a new class generalized cyclotomic quaternary sequences with period pq over Z 4 . We determine the linear complexity over F 4 and 4-adic complexity of the sequences. The results show that these sequences have high linear complexity and 4-adic complexity. [ABSTRACT FROM AUTHOR]

Understanding the properties of charge dynamics is crucial to many practical applications, such as electrochemical energy devices and transmembrane ion channels. This work proposes a Maxwell--Ampère Nernst--Planck (MANP) framework for the description of charge dynamics. The MANP model with a curl-free condition on the electric displacement is shown to be energy dissipative with respect to a convex free-energy functional, and demonstrated to be equivalent to the Poisson--Nernst--Planck model. By the energy dissipation law, the steady state of the MANP model reproduces the charge conserving Poisson--Boltzmann (PB) theory, providing an alternative energy stable approach to study the PB theory. In order to achieve the curl-free condition, a companion local curl-free relaxation algorithm, which is shown to naturally preserve the discrete Gauss's law and converge robustly with linear computational complexity, is developed for the MANP model. One of the main advantages of our development is that it can efficiently deal with space-dependent permittivity instead of solving the variable-coefficient Poisson's equation. Many-body effects such as ionic steric effects and Coulomb correlations can be incorporated within the MANP framework to derive modified MANP models for problems in which the mean-field approximation fails. Numerical results on the charge dynamics with such beyond mean-field effects in inhomogeneous dielectric environments are presented to demonstrate the performance of the MANP models in the description of charge dynamics, illustrating that the proposed MANP model provides a general framework for modeling charge dynamics. [ABSTRACT FROM AUTHOR]

A construction of binary sequences with period 4N and optimal autocorrelation magnitude has been investigated based on sampling and interleaving technique. We determine the exact value of the linear complexity of the constructed sequences according to the deep relationship among the characteristic polynomials, and show it is 2N+2. Moreover, we determine the 2-adic complexity of these sequences by the autocorrelation function, and show it can attain the maximum value. Results show that such sequences can resist both the Berlekamp-Massey attack and the Rational Approximation Algorithm, in addition are good for communication.

A quaternary sequence is said to be good if its maximum nontrivial autocorrelation is very low relative to its period. In this paper, we present some new classes of quaternary sequences with low autocorrelation of period N via two binary cyclotomic sequences, where N ≡ 1 (mod 4) is an odd prime. Furthermore, we determine the linear complexity and minimal polynomials of these quaternary sequences over F 2 2 as well. [ABSTRACT FROM AUTHOR]

Jing et al. dealed with all possible Whiteman generalized cyclotomic binary sequences $ s(a, b, c) $ with period $ N = pq $, where $ (a, b, c) \in \{0, 1\}^3 $ and $ p, q $ are distinct odd primes (Jing et al. arXiv:2105.10947v1, 2021). They have determined the autocorrelation distribution and the 2-adic complexity of these sequences in a unified way by using group ring language and a version of quadratic Gauss sums. In this paper, we determine the linear complexity and the 1-error linear complexity of $ s(a, b, c) $ in details by using the discrete Fourier transform (DFT). The results indicate that the linear complexity of $ s(a, b, c) $ is large enough and stable in most cases.

Pseudorandom sequences with large linear complexity have been widely applied in electronic countermeasures, mobile communication and cryptography. Linear complexity is considered as a primary security criterion to measure the unpredictability of pseudorandom sequences. This paper presents the linear complexity and minimal polynomial of a new family of binary sequences derived from polynomial quotients modulo an odd prime $p$ in general case. The results indicate that the sequences have high linear complexity, which means they can resist the linear attack against pseudo-noise or stream ciphers. Moreover, we generalize the result to the polynomial quotients modulo a power of $p$ in general case. Finally, we design a Gpqs stream cipher generator based on the generalized binary pseudorandom sequences to implement the sequences in hardware.

Traditional global stability measure for sequences is hard to determine because of large search space. We propose the k-error linear complexity with a zone restriction for measuring the local stability of sequences. For several classes of sequences, we demonstrate that the k-error linear complexity is identical to the k-error linear complexity within a zone, while the length of a zone is much smaller than the whole period when the k-error linear complexity is large. These sequences have periods 2 n , or 2 v r (r odd prime and 2 is primitive modulo r), or 2 v p 1 s 1 ⋯ p n s n ( p i is an odd prime and 2 is primitive modulo p i 2 , where 1 ≤ i ≤ n ) respectively. In particular, we completely determine the spectrum of 1-error linear complexity with any zone length for an arbitrary 2 n -periodic binary sequence. [ABSTRACT FROM AUTHOR]

In this paper, we propose the specific recursion formula for the generalized labeled multi-Bernoulli filter based on the track-before-detect strategy (GLMB-TBD) using a belief propagation algorithm. The proposed method aims to track multiple weak targets with superior performance. Compared to the Murty algorithm-based and Gibbs sampling-based implementation of GLMB-TBD filter, the proposed algorithm improves the tracking accuracy of multiple weak targets without pruning operation to preserve the relevant association information. The superior performance in tracking accuracy of the algorithm is validated for simulated scenarios using OSPA(2) metric. More importantly, the simulation results demonstrate that the proposed algorithm outputs both the Gibbs sampling-based version and Murty algorithm-based version in computational cost due to linear complex in the number of both Bernoulli components and measurements. [ABSTRACT FROM AUTHOR]

Recently, transformer models have demonstrated excellent performance across various intelligent applications owing to their ability to understand global context through self-attention mechanism. However, the extensively investigated multiplicative-based attention mechanism is inadequate for capturing relationship-based feature representations, as the dot product cannot depict the intricate semantic information between objects. Moreover, it has a great computational burden with a complexity of O (n 2) , due to the global feature representation capability achieved by calculating the relationship between each token within the entire feature sequence. To solve the current problem, this paper proposes a granular transformer framework with linear complexity, wherein diverse granulation functions can be employed to supersede the prevailing multiplicative relationships, and an innovative linearization methodology in the form of matrix factorization is designed to reduce the computational burden. Relying on the intricate semantics information embedded within granular structures, the capacity for feature extraction is significantly more comprehensive. Then, a novel matrix factorization methodology is developed for the linearity of granulation-based attention, accomplished by implementing separate deformable convolution sampling and using an approximate iterative algorithm based on cubic equations to calculate the Moore–Penrose inverse. The mathematical proof that our method is approximate with the complete granulation-based attention matrix is investigated in detail. Finally, the performance of Granformer, an innovative reconfiguration of plug-and-play transformer block, is evaluated on representative intelligent applications, including 3D point cloud classification, emotion recognition and sentiment analysis, and object detection. The experimental results suggest that our methodologies outperform the state-of-the-art models. [ABSTRACT FROM AUTHOR]

Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in high-speed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over $\mathbb {F}_{M}$ of $M$ -ary Sidelnikov sequence of period $q-1$ using Hasse derivative, which implies $q=p^{m}$ , $m\geq 1$ and $M|(q-1)$. The $t$ th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for $M=2$ and 3 are obtained only with some additional restrictions on $q$. Furthermore, concrete illustrations for several families of these sequences, such as $q\equiv 1\pmod {2}$ and $q\equiv 1\pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2\times 3^{\lambda }+1 (1\leq \lambda \leq 20)$ , the exact linear complexities over $\mathbb {F}_{3}$ of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods. [ABSTRACT FROM AUTHOR]

A class of binary sequences with period 2p is constructed using generalized cyclotomic classes, and their linear complexity, minimal polynomial over F q as well as 2-adic complexity are determined using Gauss period and group ring theory. The results show that the linear complexity of these sequences attains the maximum when p ≡ ± 1 (mod 8) and is equal to p+1 when p ≡ ± 3 (mod 8) over extension field. Moreover, the 2-adic complexity of these sequences is maximum. According to Berlekamp–Massey(B–M) algorithm and the rational approximation algorithm (RAA), these sequences have quite good cryptographic properties in the aspect of linear complexity and 2-adic complexity. [ABSTRACT FROM AUTHOR]

Many automatic sequences, such as the Thue-Morse sequence or the Rudin-Shapiro sequence, have some desirable features of pseudorandomness such as a large linear complexity and a small well-distribution measure. However, they also have some undesirable properties in view of certain applications. For example, the majority of possible binary patterns never appears in automatic sequences and their correlation measure of order 2 is extremely large. Certain subsequences, such as automatic sequences along squares, may keep the good properties of the original sequence but avoid the bad ones. In this survey we investigate properties of pseudorandomness and non-randomness of automatic sequences and their subsequences and present results on their behaviour under several measures of pseudorandomness including linear complexity, correlation measure of order k, expansion complexity and normality. We also mention some analogs for finite fields. [ABSTRACT FROM AUTHOR]

Binary PN-sequences generated by LFSRs exhibit good statistical properties; however, due to their intrinsic linearity, they are not suitable for cryptographic applications. In order to break such a linearity, several approaches can be implemented. For example, one can interleave several PN-sequences to increase the linear complexity. In this work, we present a deep randomness study of the resultant sequences of interleaving binary PN-sequences coming from different characteristic polynomials with the same degree. We analyze the period and the linear complexity, as well as many other important cryptographic properties of such sequences. [ABSTRACT FROM AUTHOR]

We bound the number of distinct minimal subsystems of a given transitive subshift of linear complexity, continuing work of Ormes and Pavlov [On the complexity function for sequences which are not uniformly recurrent. Dynamical Systems and Random Processes (Contemporary Mathematics, 736). American Mathematical Society, Providence, RI, 2019, pp. 125--137]. We also bound the number of generic measures such a subshift can support based on its complexity function. Our measure-theoretic bounds generalize those of Boshernitzan [A unique ergodicity of minimal symbolic flows with linear block growth. J. Anal. Math.44(1) (1984), 77–96] and are closely related to those of Cyr and Kra [Counting generic measures for a subshift of linear growth. J. Eur. Math. Soc.21(2) (2019), 355–380]. [ABSTRACT FROM AUTHOR]

We introduce rational complexity, a new complexity measure for binary sequences. The sequence s ∈ Bω is considered as binary expansion of a real fraction s ≡ ∑ k ∈ ℕ s k 2 − k ∈ [ 0 , 1 ] ⊂ ℝ . We compute its continued fraction expansion (CFE) by the Binary CFE Algorithm, a bitwise approximation of s by binary search in the encoding space of partial denominators, obtaining rational approximations r of s with r → s. We introduce Feedback in ℚ Shift Registers (F ℚ SRs) as the analogue of Linear Feedback Shift Registers (LFSRs) for the linear complexity L, and Feedback with Carry Shift Registers (FCSRs) for the 2-adic complexity A. We show that there is a substantial subset of prefixes with "typical" linear and 2-adic complexities, around n/2, but low rational complexity. Thus the three complexities sort out different sequences as non-random. [ABSTRACT FROM AUTHOR]