The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

New reliability bounds for coherent systems

In 1970, Esary and Proschan proposed simple formulae for the system reliability lower bound and system reliability upper bound. Their formulae of reliability bounds have been classic and have been incorporated into almost all recent textbooks on reliability. In this paper, we decompose a coherent system into several consecutive-k-out-of-n : F(G) systems, and then based upon their exact formulae for system reliabilities, we develop new formulae for both reliability lower bound and reliability upper bound for the coherent system. In addition, we show that the new proposed reliability bounds are superior to those of Esary and Proschan for all coherent systems when the minimal cut/path sets have elements in common. Numerical results are reported, compared and discussed for various systems.     

On the relative profiles of a linear code and a subcode

Relative dimension/length profile (RDLP), inverse relative dimension/length profile (IRDLP) and relative length/dimension profile (RLDP) are equivalent sequences of a linear code and a subcode. The concepts were applied to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. The equivocation to the adversary is described by IRDLP and upper-bounded by the generalized Singleton bound on IRDLP. Recently, RLDP was also extended in wiretap network II for secrecy control of network coding. In this paper, we introduce new relations and bounds about the sequences. They not only reveal new connections among known results but also find applications in trellis complexities of linear codes. The state complexity profile of a linear code and that of a subcode can be bounded from each other, which is particularly useful when a tradeoff among coding rate, error-correcting capability and decoding complexity is considered. Furthermore, a unified framework is proposed to derive bounds on RDLP and IRDLP from an upper bound on RLDP. We introduce three new upper bounds on RLDP and use some of them to tighten the generalized Singleton bounds by applying the framework. The approach is useful to improve equivocation estimation in the wiretap channel of type II with illegitimate parties.     

Ranking lower bounds for the bin-packing problem

In this paper, we evaluate different known lower bounds for the bin-packing problem including linear programming relaxation (LP), Lagrangean relaxation (LR), Lagrangean decomposition (LD) and the Martello–Toth (MT) [Martello, S., Toth, P., Knapsack Problems: Algorithms and Computer Implementations, Wiley, New York, 1990] lower bounds. We give conditions under which Lagrangean bounds are superior to the LP bound, show that Lagrangean decomposition (LD) yields the same bound as Lagrangean relaxation (LR) and prove that the MT lower bound is a Lagrangean bound evaluated at a finite set of Lagrange multipliers; hence, it is no better than the LR and LD lower bounds.     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.     

Quadratic model for allocating operational budget in public and nonprofit organizations

We develop a quadratic model for allocating operational budgets in public and nonprofit organizations. The allocations for each organizational unit have lower and upper bounds. The objective function is to minimize the weighted sum of the quadratic deviations of each allocation from its bounds. The optimal allocations are mostly around the midpoint between the bounds. A simple algorithm is presented to derive the solution. The new quadratic model is compared to the familiar linear model for budget allocation, which almost always, provides extreme allocations on the bounds: for some units on the upper bound, while for others, on the lower bound. We perform sensitivity analyses, and resolve special cases of the model with closed form solution. Moreover, we show various properties of the quadratic budget allocation model and prove that its fairness index is higher than that of the linear model. The model, with its variants, was actually used for allocating budgets in various university setups; some examples are presented here.     

A scenario generation-based lower bounding approach for stochastic scheduling problems

In this paper, we investigate scenario generation methods to establish lower bounds on the optimal objective value for stochastic scheduling problems that contain random parameters with continuous distributions. In contrast to the Sample Average Approximation (SAA) approach, which yields probabilistic bound values, we use an alternative bounding method that relies on the ideas of discrete bounding and recursive stratified sampling. Theoretical support is provided for deriving exact lower bounds for both expectation and conditional value-at-risk objectives. We illustrate the use of our method on the single machine total weighted tardiness problem. The results of our numerical investigation demonstrate good properties of our bounding method, compared with the SAA method and an earlier discrete bounding method.     

Lower Bounds for the Rate of Convergence of Dynamic Reconstruction Algorithms for Distributed-Parameter Systems

We obtain lower bounds for the rate of convergence of reconstruction algorithms for distributed-parameter systems of parabolic type. In the case of a pointwise constraint on control for known reconstruction algorithms, we establish a lower bound on the rate of convergence, which shows that, given certain conditions, for each solution of the system one can choose such a collection of measurements so that the reconstruction error will not be less than a certain value. In the case of unbounded controls, we obtain lower bounds for a possible reconstruction error for each trajectory as well as for a given set of trajectories. For a system of special form, we construct an algorithm for which we obtain upper and lower bounds for accuracy having identical order for a specific choice of matching of the parameters.     

Recursive lower and dual upper bounds for Bermudan-style options

Although Bermudan options are routinely priced by simulation and least-squares methods using lower and dual upper bounds, the latter are hardly optimized. In this paper, we optimize recursive upper bounds, which are more tractable than the original/nonrecursive ones, and derive two new results: (1) An upper bound based on (a martingale that depends on) stopping times is independent of the next-stage exercise decision and hence cannot be optimized. Instead, we optimize the recursive lower bound, and use its optimal recursive policy to evaluate the upper bound as well. (2) Less time-intensive upper bounds that are based on a continuation-value function only need this function in the continuation region, where this continuation value is less nonlinear and easier to fit (than in the entire support). In the numerical exercise, both upper bounds improve over state-of-the-art methods (including standard least-squares and pathwise optimization). Specifically, the very small gap between the lower and the upper bounds derived in (1) implies the recursive policy and the associated martingale are near optimal, so that these two specific lower/upper bounds are hard to improve, yet the upper bound is tighter than the lower bound.     

Lower bounds on two-terminal network reliability

Computing the probability that two nodes in a probabilistic network are connected is a well-known computationally difficult problem. Two strategies are devised for obtaining lower bounds on the connection probability for two terminals. The first improves on the Kruskal-Katona bound by using efficient computations of small pathsets. The second strategy employs efficient algorithms for finding edge-disjoint paths. The resulting bounds are compared; while the edge-disjoint path bounds typically outperform the Kruskal-Katona bounds, they do not always do so. Finally, a method is outlined for developing a uniform bound which combines both strategies.     

Finding lower bounds on the complexity of secret sharing schemes by linear programming

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.     

Bounds and estimates on the effective properties for nonlinear composites

In this paper we derive lower bounds and upper bounds on the effective properties for nonlinear heterogeneous systems. The key result to obtain these bounds is to derive a variational principle, which generalizes the variational principle by P. Ponte Castaneda from 1992. In general, when the Ponte Castaneda variational principle is used one only gets either a lower or an upper bound depending on the growth conditions. In this paper we overcome this problem by using our new variational principle together with the bounds presented by Lukkassen, Persson and Wall in 1995. Moreover, we also present some examples where the bounds are so tight that they may be used as a good estimate of the effective behavior.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

The behaviour of probabilistic error bounds in floating

In this paper we present a probabilistic approach for the estimation of realistic error bounds appearing in the execution of basic algebraic floating point operations. Experimental results are carried out for the extended product, the extended sum, the inner product of random normalised numbers, the product of random normalised matrices and the solution of lower triangular systems The ordinary and probabilistic bounds are calculated for all the above processes and generally in all the executed examples the probabilistic bounds are much more realistic.     

Lower Bounds for Measurable Chromatic Numbers

The Lovász theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces. In particular we consider distance graphs on the unit sphere. There we transform the original infinite semidefinite program into an infinite linear program which then turns out to be an extremal question about Jacobi polynomials which we solve explicitly in the limit. As an application we derive new lower bounds for the measurable chromatic number of the Euclidean space in dimensions 10, . . . , 24 and we give a new proof that it grows exponentially with the dimension.     

On the Meany inequality with applications to convergence analysis of several row-action iteration methods

The Meany inequality gives an upper bound in the Euclidean norm for a product of rank-one projection matrices. In this paper we further derive a lower bound related to this inequality. We discuss the internal relationship between the upper bounds given by the Meany inequality and by the inequality in Smith et al. (Bull Am Math Soc 83:1227–1270, 1977) in the finite dimensional real linear space. We also generalize the Meany inequality to the block case. In addition, by making use of the block Meany inequality, we improve existing results and establish new convergence theorems for row-action iteration schemes such as the block Kaczmarz and the Householder–Bauer methods used to solve large linear systems and least-squares problems.     

Circuit lower bounds and linear codes

In 1977, Valiant proposed a graph-theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to proving lower bounds on the rigidity of a matrix, a notion that he introduced in that paper. The largest lower bound for an explicitly given matrix is due to J. Friedman, who proved a lower bound on the rigidity of the generator matrices of error-correcting codes over finite fields. He showed that the proof can be interpreted as a bound on a certain parameter defined for all linear spaces of finite dimension. In this note, we define another parameter that can be used to prove lower bounds on circuits with linear gates. Our parameter may be larger than Friedman’s, and it seems incomparable with rigidity, hence it may be easier to prove a lower bound using this notion. Bibliography: 14 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 188–204.     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.