Complexity Lower Bounds for Approximation Algebraic Computation Trees

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.     

Simplified Lower Bounds for Polynomials with Algebraic Coefficients

We present a very simple method to prove lower bounds for the nonscalar complexity of polynomials with algebraic coefficients.     

关于拓扑熵下界的两点注记

设ｆ：Ｘ→Ｘ是紧连通多面体自映射，应用Ｎｉｅｌｓｅｎ不动点理论，我们给出了ｆ的拓扑熵ｈ（ｆ）的一个更好下界。另外，若ｆ：Ｔ^m→T^m是ｍ－环面自映射，我们还得到了ｌｏｇＮ^∞（ｆ）是{h(g)|g≈f:T^m→T^m}的下确界的一个充要条件，这里Ｎ（ｆ）是ｆ的渐近Ｎｉｅｌｓｅｎ数，从而局部解答了姜伯驹教授提出的一个问题。     

Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T)=O(k⋅n ^1/k )⋅w(MST(M)), and a spanning tree T′ with weight w(T′)=O(k)⋅w(MST(M)) and unweighted diameter O(k⋅n ^1/k ). These trees also achieve an optimal maximum degree. Furthermore, we demonstrate that these trees can be constructed efficiently.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

离散时间代数Riccati方程的解矩阵的下界与上界

本文讨论离散时间代数Ｒｉｃｃａｔｉ方程ＡＴＸＡ－Ｘ－（ＡＴＸＢ＋Ｌ）（Ｒ＋ＢＴＸＢ）＾－１（ＬＴ＋ＢＴＸＡ）＋Ｑ＝０的唯一对称正定解的上界和下界。     

离散代数Riccati方程解的上下界

给出离散代数Ｒｉｃｃａｔｉ方程解的迹的上界和下界计算公式,较现有结果相比,该结果具有较高的估计精度,数值算例表明该方法的有效性。     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

Lower Bounds in Real Algebraic Geometry and Orientability of Real Toric Varieties

The real solutions to a system of sparse polynomial equations may be realized as a fiber of a projection map from a toric variety. When the toric variety is orientable, the degree of this map is a lower bound for the number of real solutions to the system of equations. We strengthen previous work by characterizing when the toric variety is orientable. This is based on work of Nakayama and Nishimura, who characterized the orientability of smooth real toric varieties.     

On Lower Bounds For Covering Codes

We study lower bounds on K(n,R), the minimum number of codewords of any binary code of length n such that the Hamming spheres of radius R with center at codewords cover the Hamming space . We generalize Honkala's idea toobtain further improvements only by using some simple observationsof Zhang's result. This leads to nineteen improvements of thelower bound on K(n,R) within the range of .     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

On Lower Bounds for the Redundancy of Optimal Codes

The problem of providing bounds on the redundancy of an optimal code for a discrete memoryless source in terms of the probability distribution of the source, has been extensively studied in the literature. The attention has mainly focused on binary codes for the case when the most or the least likely source letter probabilities are known. In this paper we analyze the relationships among tight lower bounds on the redundancy r. Let r _D,i(x) be the tight lower bound on r for D-ary codes in terms of the value x of the i-th most likely source letter probability. We prove that _D,i-1(x) _D,i(x) for all possible x and i. As a consequence, we can bound the redundancy when only the value of a probability (but not its rank) is known. Another consequence is a shorter and simpler proof of a known bound. We also provide some other properties of tight lower bounds. Finally, we determine an achievable lower bound on r in terms of the least likely source letter probability for D 3, generalizing the known bound for the case D = 2.     

On Lower Bounds for the Chromatic Number of Spheres

Mathematical Notes - Estimates of the chromatic numbers of spheres are studied. The optimality of the choice of the parameters of the linear-algebraic method used to obtain these estimates is...     

Algebraic Topological Closure Operators

For any closure operator c there is a T_o-closure operator whose lattice of closed subsets are isomorphic to that of c. A correspondence between algebraic topological (T_o) closure operators on a nonempty set X and pre-orderes (partial orders) on X is established. Equivalent conditions are obtained for a T_o-lattice to be a complete atomic Boolean algebra and for the lattice of closed subsets of an algebraic topological closure operator to be a complete atomic Boolean algebra. Further it is proved that a complete lattice is an algebraic T_o-lattice if and only if it is isomorphic to the lattice of closed subsets of some algebraic topological closure operator on a suitable set.AMS Subject Classification (1991): 06A23, 54D65.     

Lower Bounds for Covering Problems

In this paper we present an (nlogn) lower bound proof for several covering problems including the optimal line bipartition problem, min-max covering by two axis parallel rectangles, discrete and continuous two-center problems, two-line center problem, etc. Our proofs are based on using the rotational reduce technique and well-known lower bound for the maximal gap problem.     

Lower Bounds for Transversal Covers

A transversal cover is a set of gk points in k disjoint groups of size g and a collection of b transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. A central question is to determine, for given g, the minimum possible b for fixed k, or, alternatively, the maximum k for fixed b. The case g=2 was investigated and completely solved by Sperner sperner:28, Rényi renyi:71, Katona katona:73, and Kleitman and Spencer kleitman:73. For arbitrary g, asymptotic results are known but little is understood for small values of k. Constructions exist but these only produce upper bounds on b. The present article is concerned with lower bounds on b. We develop three general lower bounds on b for fixedg and k. The first one is proved using one of the principal constructions brett:97a, the second comes from the study of intersecting set-systems, and the third is shown by a set packing argument. In addition, we investigate upper bounds on k for small fixed b. This proves useful to reduce or eliminate the gap between lower and upper bounds on b for some transversal covers with small k.     

Lower Bounds for Catalan's Equation

This paper begins with a short historical survey on Catalan's equation, namely x^p-y^q=1, where p andq are prime numbers and x, y are non-zero rational integers. It is conjectured that the only solution is the trivial solution 3²-2³=1. We prove that there is no non-trivial solution with p orq smaller than 30000. The tools to reach such a result are presented. A crucial role is played by a recent estimate of linear forms in two logarithms obtained by Laurent, Mignotte and Nestrenko. The criteria used are also quite recent. We give information on the enormous amount of computation needed for the verification.     

Ramsey数的几个新下界公式

本文通过构造循环图,得到并证明了公式:r(3,q)≥5(q-3)+2,r(3,q)≥7(q-5)+2,(q为奇数),又由所给引理:若r(l_1,k_1)>t_1,r(l_2,k_2)>t_2,则r(l_1-1·l_2-1+1,k_1-1·k_2-1+1)>t_1t_2,归纳出又一公式:r(3~n+1,3~n+1)≥17~n+1     

Lower Bounds for Cubical Pseudomanifolds

It is verified that the number of vertices in a d-dimensional cubical pseudomanifold is at least 2 ^d+1. Using Adin’s cubical h-vector, the generalized lower bound conjecture is established for all cubical 4-spheres, as well as for some special classes of cubical spheres in higher dimensions.