Matricial Model for the Study of Lower Bounds

Let V be an array. The range query problem concerns the design of data structures for implementing the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower bound is near optimal – in terms of asymptotic complexity.

Upper and Lower Bounds for Ruin Probability

In this note we discuss upper and lower bound for the ruin probability in an insurance model with very heavy-tailed claims and interarrival times.

Lower Bounds on the Directed Sweepwidth of Planar Shapes

We investigate a recently introduced width measure of planar shapes called sweepwidth and prove a lower bound theorem on the sweepwidth.

Improvements to the design of Litesteel Beams undergoing lateral distortional buckling

An Australian manufacturer has recently developed an innovative group of cold-formed steel hollow flange sections, one of them is LiteSteel Beams (LSBs). The LSB sections are produced from thin and high strength steels by a patented manufacturing process involving simultaneous cold-forming and dual electric resistance welding. They have a unique geometry consisting of rectangular hollow flanges and a relatively slender web. The LSB flexural members are subjected to lateral distortional buckling effects and hence their capacities are reduced for intermediate spans. The current design rules for lateral distortional buckling were developed based on the lower bound of numerical and experimental results. The effect of LSB section geometry was not considered although it could influence the lateral distortional buckling performance. Therefore an accurate finite element model of LSB flexural members was developed and validated using experimental and finite strip analysis results. It was then used to investigate the effect of LSB geometry. The extensive moment capacity data thus developed was used to develop improved design rules for LSBs with one of them considering the LSB geometry effects through a modified slenderness parameter. The use of the new design rules gave higher lateral distortional buckling capacities for LSB sections with intermediate slenderness. The new design rule is also able to accurately predict the lateral distortional buckling moment capacities of other hollow flange beams (HFBs).

Computed success rates of various carrier phase integer estimation solutions and their comparison with statistical success rates

The success rate of carrier phase ambiguity resolution (AR) is the probability that the ambiguities are successfully fixed to their correct integer values. In existing works, an exact success rate formula for integer bootstrapping estimator has been used as a sharp lower bound for the integer least squares (ILS) success rate. Rigorous computation of success rate for the more general ILS solutions has been considered difficult, because of complexity of the ILS ambiguity pull-in region and computational load of the integration of the multivariate probability density function. Contributions of this work are twofold. First, the pull-in region mathematically expressed as the vertices of a polyhedron is represented by a multi-dimensional grid, at which the cumulative probability can be integrated with the multivariate normal cumulative density function (mvncdf) available in Matlab. The bivariate case is studied where the pull-region is usually defined as a hexagon and the probability is easily obtained using mvncdf at all the grid points within the convex polygon. Second, the paper compares the computed integer rounding and integer bootstrapping success rates, lower and upper bounds of the ILS success rates to the actual ILS AR success rates obtained from a 24 h GPS data set for a 21 km baseline. The results demonstrate that the upper bound probability of the ILS AR probability given in the existing literatures agrees with the actual ILS success rate well, although the success rate computed with integer bootstrapping method is a quite sharp approximation to the actual ILS success rate. The results also show that variations or uncertainty of the unit–weight variance estimates from epoch to epoch will affect the computed success rates from different methods significantly, thus deserving more attentions in order to obtain useful success probability predictions.

Correction to “The Importance of Convexity in Learning With Squared Loss” [Sep 98 1974-1980]

The paper "the importance of convexity in learning with squared loss" gave a lower bound on the sample complexity of learning with quadratic loss using a nonconvex function class. The proof contains an error. We show that the lower bound is true under a stronger condition that holds for many cases of interest.

Adaptive online gradient descent

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between [square root T] and [log T]. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Optimising a coal rail network under capacity constraints

This research deals with an innovative methodology for optimising the coal train scheduling problem. Based on our previously published work, generic solution techniques are developed by utilising a “toolbox” of standard well-solved standard scheduling problems. According to our analysis, the coal train scheduling problem can be basically modelled a Blocking Parallel-Machine Job-Shop Scheduling (BPMJSS) problem with some minor constraints. To construct the feasible train schedules, an innovative constructive algorithm called the SLEK algorithm is proposed. To optimise the train schedule, a three-stage hybrid algorithm called the SLEK-BIH-TS algorithm is developed based on the definition of a sophisticated neighbourhood structure under the mechanism of the Best-Insertion-Heuristic (BIH) algorithm and Tabu Search (TS) metaheuristic algorithm. A case study is performed for optimising a complex real-world coal rail system in Australia. A method to calculate the lower bound of the makespan is proposed to evaluate results. The results indicate that the proposed methodology is promising to find the optimal or near-optimal feasible train timetables of a coal rail system under network and terminal capacity constraints.

A hybrid smoothed finite element method (H-SFEM) to solid mechanics problems

In this paper, a hybrid smoothed finite element method (H-SFEM) is developed for solid mechanics problems by combining techniques of finite element method (FEM) and Node-based smoothed finite element method (NS-FEM) using a triangular mesh. A parameter is equipped into H-SFEM, and the strain field is further assumed to be the weighted average between compatible stains from FEM and smoothed strains from NS-FEM. We prove theoretically that the strain energy obtained from the H-SFEM solution lies in between those from the compatible FEM solution and the NS-FEM solution, which guarantees the convergence of H-SFEM. Intensive numerical studies are conducted to verify these theoretical results and show that (1) the upper and lower bound solutions can always be obtained by adjusting ; (2) there exists a preferable at which the H-SFEM can produce the ultrasonic accurate solution.

Experimental studies of hollow flange channel beams subject to combined bending and shear actions

This paper presents the details of an experimental study of a cold-formed steel hollow flange channel beam known as LiteSteel Beam (LSB) subject to combined bending and shear actions. The LSB sections are produced by a patented manufacturing process involving simultaneous cold-forming and electric resistance welding. Due to the geometry of the LSB, as well as its unique residual stress characteristics and initial geometric imperfections resultant of manufacturing processes, much of the existing research for common cold-formed steel sections is not directly applicable to LSB. Experimental and numerical studies have been carried out to evaluate the behaviour and design of LSBs subject to pure bending actions and predominant shear actions. To date, however, no investigation has been conducted into the strength of LSB sections under combined bending and shear actions. Combined bending and shear is especially prevalent at the supports of continuous span and cantilever beams, where the interaction of high shear force and bending moment can reduce the capacity of a section to well below that for the same section subject only to pure shear or moment. Hence experimental studies were conducted to assess the combined bending and shear behaviour and strengths of LSBs. Eighteen tests were conducted and the results were compared with current AS/NZS 4600 and AS 4100 design rules. AS/NZS 4600 design rules were shown to grossly underestimate the combined bending and shear capacities of LSBs and hence two lower bound design equations were proposed based on experimental results. Use of these equations will significantly improve the confidence and cost-effectiveness of designing LSBs for combined bending and shear actions.

Unconditionally secure disjointness tests for private datasets

We present two unconditional secure protocols for private set disjointness tests. In order to provide intuition of our protocols, we give a naive example that applies Sylvester matrices. Unfortunately, this simple construction is insecure as it reveals information about the intersection cardinality. More specifically, it discloses its lower bound. By using the Lagrange interpolation, we provide a protocol for the honest-but-curious case without revealing any additional information. Finally, we describe a protocol that is secure against malicious adversaries. In this protocol, a verification test is applied to detect misbehaving participants. Both protocols require O(1) rounds of communication. Our protocols are more efficient than the previous protocols in terms of communication and computation overhead. Unlike previous protocols whose security relies on computational assumptions, our protocols provide information theoretic security. To our knowledge, our protocols are the first ones that have been designed without a generic secure function evaluation. More important, they are the most efficient protocols for private disjointness tests in the malicious adversary case.

Does counting still count? Revisiting the security of counting based user authentication protocols against statistical attacks

At NDSS 2012, Yan et al. analyzed the security of several challenge-response type user authentication protocols against passive observers, and proposed a generic counting based statistical attack to recover the secret of some counting based protocols given a number of observed authentication sessions. Roughly speaking, the attack is based on the fact that secret (pass) objects appear in challenges with a different probability from non-secret (decoy) objects when the responses are taken into account. Although they mentioned that a protocol susceptible to this attack should minimize this difference, they did not give details as to how this can be achieved barring a few suggestions. In this paper, we attempt to fill this gap by generalizing the attack with a much more comprehensive theoretical analysis. Our treatment is more quantitative which enables us to describe a method to theoretically estimate a lower bound on the number of sessions a protocol can be safely used against the attack. Our results include 1) two proposed fixes to make counting protocols practically safe against the attack at the cost of usability, 2) the observation that the attack can be used on non-counting based protocols too as long as challenge generation is contrived, 3) and two main design principles for user authentication protocols which can be considered as extensions of the principles from Yan et al. This detailed theoretical treatment can be used as a guideline during the design of counting based protocols to determine their susceptibility to this attack. The Foxtail protocol, one of the protocols analyzed by Yan et al., is used as a representative to illustrate our theoretical and experimental results.

Known and chosen key differential distinguishers for block ciphers

In this paper we investigate the differential properties of block ciphers in hash function modes of operation. First we show the impact of differential trails for block ciphers on collision attacks for various hash function constructions based on block ciphers. Further, we prove the lower bound for finding a pair that follows some truncated differential in case of a random permutation. Then we present open-key differential distinguishers for some well known round-reduced block ciphers.

Efficient disjointness tests for private datasets

We present efficient protocols for private set disjointness tests. We start from an intuition of our protocols that applies Sylvester matrices. Unfortunately, this simple construction is insecure as it reveals information about the cardinality of the intersection. More specifically, it discloses its lower bound. By using the Lagrange interpolation we provide a protocol for the honest-but-curious case without revealing any additional information. Finally, we describe a protocol that is secure against malicious adversaries. The protocol applies a verification test to detect misbehaving participants. Both protocols require O(1) rounds of communication. Our protocols are more efficient than the previous protocols in terms of communication and computation overhead. Unlike previous protocols whose security relies on computational assumptions, our protocols provide information theoretic security. To our knowledge, our protocols are first ones that have been designed without a generic secure function evaluation. More importantly, they are the most efficient protocols for private disjointness tests for the malicious adversary case.

Numerical studies and design of hollow flange channel beams subject to combined bending and shear actions

LiteSteel beam (LSB) is a cold-formed steel hollow flange channel section produced using a patented manufacturing process involving simultaneous cold-forming and dual electric resistance welding. It is commonly used as floor joists and bearers in residential, industrial and commercial buildings. Design of the LSB is governed by the Australian cold-formed steel structures code, AS/NZS 4600. Due to the geometry of the LSB, as well as its unique residual stress characteristics and initial geometric imperfections resultant of manufacturing processes, currently available design equations for common cold-formed sections are not directly applicable to the LSB. Many research studies have been carried out to evaluate the behaviour and design of LSBs subject to pure bending actions and predominant shear actions. To date, however, no investigation has been conducted into the strength of LSB sections under combined bending and shear actions. Hence experimental and numerical studies were conducted to assess the combined bending and shear behaviour of LSBs. Finite element models of LSBs were developed to simulate their combined bending and shear behaviour and strength of LSBs. They were then validated by comparing the results with available experimental test results and used in a detailed parametric study. The results from experimental and finite element analyses were compared with current AS/NZS 4600 and AS 4100 design rules. Both experimental and numerical studies show that the AS/NZS 4600 design rule based on circular interaction equation is conservative in predicting the combined bending and shear capacities of LSBs. This paper presents the details of the numerical studies of LSBs and the results. In response to the inadequacies of current approaches to designing LSBs for combined bending and shear, two lower bound design equations are proposed in this paper.