On linear complexity of binary lattices,II

The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.     

On the linear complexity of binary threshold sequences derived from Fermat quotients

We determine the linear complexity of a family of p ²-periodic binary threshold sequences derived from Fermat quotients modulo an odd prime p, where p satisfies ${2^{p-1} \not\equiv 1 ({\rm mod}\, {p^2})}$ . The linear complexity equals p ² ? p or p ² ? 1, depending whether ${p \equiv 1}$ or 3 (mod 4). Our research extends the results from previous work on the linear complexity of the corresponding binary threshold sequences when 2 is a primitive root modulo p ². Moreover, we present a partial result on their linear complexities for primes p with ${2^{p-1} \equiv 1 ({\rm mod} \,{p^2})}$ . However such so called Wieferich primes are very rare.     

On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length 2p m

In this article, new classes of generalized cyclotomic binary sequences with period 2p ^m are proposed. We determine the linear complexity and autocorrelation of these sequences. The results show that the proposed generalized cyclotomic binary sequences have high linear complexity, but do not have desirable autocorrelation properties.     

On new measures of pseudorandomness of binary lattices

Hubert, Mauduit and Sárközy introduced the pseudorandom measure of order ? of binary lattices. This measure studies the pseudorandomness only on box lattices of very special type. In certain applications one may need measures covering a more general situation. In this paper the line measure and the convex measure are introduced.     

FCSR序列的线性复杂度

§ 1　 IntroductionFeedback with carry shift register(FCSR) was first introduced by Klapper andGoresky in1 994[1 ] .The main idea of FCSR is to add a memory to linearfeedback shiftreg-ister(LFSR) .The structure is depicted in Fig.1 ,Fig.1where mn- 1 ∈Z,ai,qi∈ { 0 ,1 } and qr=1 .We refer to mn- 1 as memory,(mn- 1 ,an- 1 ,...,an- r)as state,r=log(q+ 1 ) as length,and q=-1 + q1 · 2 + ...+ qr· 2 ras connection integerof FCSR.The operation of the shiftregister is defined as follows:(1 …     

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.     

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.     

On the complexity of minmax regret linear programming

We consider linear programming problems with uncertain objective function coefficients. For each coefficient of the objective function, an interval of uncertainty is known, and it is assumed that any coefficient can take on any value from the corresponding interval of uncertainty, regardless of the values taken by other coefficients. It is required to find a minmax regret solution. This problem received considerable attention in the recent literature, but its computational complexity status remained unknown. We prove that the problem is strongly NP-hard. This gives the first known example of a minmax regret optimization problem that is NP-hard in the case of interval-data representation of uncertainty but is polynomially solvable in the case of discrete-scenario representation of uncertainty.     

Communication complexity in lattices

The communcation complexity of functions defined in lattices is bounded from above and below, hereby generalizing former results of Lovasz [1] and Ahlswede and Cai [2]. Especially in geometric lattices, upper and lower bound often differ by at most one bit.     

The linear complexity of a class of binary sequences with optimal autocorrelation

Binary sequences with optimal autocorrelation and large linear complexity have important applications in cryptography and communications. Very recently, a class of binary sequences of period 4p with optimal autocorrelation was proposed by interleaving four suitable Ding–Helleseth–Lam sequences (Des. Codes Cryptogr.,  https://doi.org/10.1007/s10623-017-0398-5), where p is an odd prime with \(p \equiv 1(\bmod 4)\). The objective of this paper is to determine the minimal polynomial and the linear complexity of this class of binary optimal sequences via a sequence polynomial approach. It turns out that this class of sequences has quite good linear complexity.     

A counterexample concerning the 3-error linear complexity of 2 n -periodic binary sequences

In this article, we present a counterexample to Theorem 4.2 and Theorem 5.2 by Kavuluru (Des Codes Cryptogr 53:75–97, 2009). We conclude that the counting functions for the number of 2 ⁿ -periodic binary sequences with fixed 3-error linear complexity by Kavuluru are not correct.     

On the topological linear spaces whose subspace lattices are modular

LetX be a topological linear space and letL(X) be a lattice of all closed subspaces ofX. We show that in many cases the modularity ofL(X) implies that every bounded subset ofX is finite-dimensional. We derive some topological consequences of the latter result. Due to the significance of the modularity condition forL(X) in quantum axiomatics and elswhere (see [1,14,15]) results also might find application outside the realm of topological linear spaces.     

On the complexity of locating linear facilities in the plane

We consider the computational complexity of linear facility location problems in the plane, i.e., given n demand points, one wishes to find r lines so as to minimize a certain objective-function reflecting the need of the points to be close to the lines. It is shown that it is NP-hard to find r lines so as to minimize any isotone function of the distances between given points and their respective nearest lines. The proofs establish NP-hardness in the strong sense. The results also apply to the situation where the demand is represented by r lines and the facilities by n single points.     

On the weight distribution of random binary linear codes

We investigate the weight distribution of random binary linear codes. For 0 < λ < 1 and n→∞ pick uniformly at random λn vectors in and let be the orthogonal complement of their span. Given 0 < γ < 1/2 with 0 < λ < h(γ) let X be the random variable that counts the number of words in C of Hamming weight γn. In this paper we determine the asymptotics of the moments of X of all orders .     

On the joint linear complexity profile of explicit inversive multisequences

We prove lower bounds on the joint linear complexity profile of multisequences obtained by explicit inversive methods and show that for some suitable choices of parameters these joint linear complexity profiles are close to be perfect.     

On the complexity of linear boolean operators with thin matrices

Under consideration is the problem of constructing a square Booleanmatrix A of order n without “rectangles” (it is a matrix whose every submatrix of the elements that are in any two rows and two columns does not consist of 1s). A linear transformation modulo two defined by A has complexity o(ν(A) − n) in the base {⊕}, where ν(A) is the weight of A, i.e., the number of 1s (the matrices without rectangles are called thin). Two constructions for solving this problem are given. In the first construction, n = p ² where p is an odd prime. The corresponding matrix H _p has weight p ³ and generates the linear transformation of complexity O(p ² log p log log p). In the second construction, the matrix has weight nk where k is the cardinality of a Sidon set in ℤ _n . We may assume that

On the complexity of linear programming under finite precision arithmetic

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the conditioning of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of good numerical behavior of the logarithmic barrier method, in the sense that a problem instance twice as hard as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research has been supported through grants from Fundación Andes, under agreement C12021/7, and FONDECYT (project number 1930948).     

On the complexity of following the central path of linear programs by linear extrapolation II

A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, ) of steps needed to go from an initial pointx(R) to a final pointx(), R>>0, by an integral of the local weighted curvature of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm log(R/), where < 1/2 e.g. = 1/4 or = 3/8 (note that = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.On leave from the Institute of Mathematics, Eötvös University Budapest, H-1080 Budapest, Hungary.