D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Resolvent Estimates for Operators Belonging to Exponential Classes

For a, α > 0 let E(a, α) be the set of all compact operators A on a separable Hilbert space such that s _n (A) = O(exp(-an^α)), where s _n (A) denotes the n-th singular number of A. We provide upper bounds for the norm of the resolvent (zI − A)⁻¹ of A in terms of a quantity describing the departure from normality of A and the distance of z to the spectrum of A. As a consequence we obtain upper bounds for the Hausdorff distance of the spectra of two operators in E(a, α).      

Regev’s and Amitsur’s conjectures for codimensions of generalized polynomial identities

Let A be a finite-dimensional associative algebra over a field of characteristic 0. Then there exist C ∈ ℚ₊ and t ∈ ℤ₊ such that gc _n (A) ∼ Cn ^t d ⁿ as n → ∞, where d = PIexp(A). In particular, Amitsur’s and Regev’s conjectures hold for the codimensions gc _n (A) of generalized polynomial identities.     

The algebra ofG-relations

In this paper, we study a tower {A _n ^G: n} ≥ 1 of finite-dimensional algebras; here, G represents an arbitrary finite group,d denotes a complex parameter, and the algebraA _n ^G(d) has a basis indexed by ‘G-stable equivalence relations’ on a set whereG acts freely and has 2n orbits. We show that the algebraA _n ^G(d) is semi-simple for all but a finite set of values ofd, and determine the representation theory (or, equivalently, the decomposition into simple summands) of this algebra in the ‘generic case’. Finally we determine the Bratteli diagram of the tower {A _n ^G(d): n} ≥ 1 (in the generic case).     

Max-Min Problems on the Ranks and Inertias of the Matrix Expressions <Emphasis Type="Italic">A</Emphasis>−<Emphasis Type="Italic">BXC</Emphasis>±(<Emphasis Type="Italic">BXC</Emphasis>)<Superscript>∗</Superscript> with Applications

We introduce a simultaneous decomposition for a matrix triplet (A,B,C ^∗), where A=±A ^∗ and (⋅)^∗ denotes the conjugate transpose of a matrix, and use the simultaneous decomposition to solve some conjectures on the maximal and minimal values of the ranks of the matrix expressions A−BXC±(BXC)^∗ with respect to a variable matrix X. In addition, we give some explicit formulas for the maximal and minimal values of the inertia of the matrix expression A−BXC−(BXC)^∗ with respect to X. As applications, we derive the extremal ranks and inertias of the matrix expression D−CXC ^∗ subject to Hermitian solutions of a consistent matrix equation AXA ^∗=B, as well as the extremal ranks and inertias of the Hermitian Schur complement D−B ^∗ A ^∼ B with respect to a Hermitian generalized inverse A ^∼ of A. Various consequences of these extremal ranks and inertias are also presented in the paper.     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Equivalent Characterizations for Boundedness of Maximal Singular Integrals on ax+b-Groups

Let (S,d,ρ) be the affine group ℝ ⁿ ⋉ℝ⁺ endowed with the left-invariant Riemannian metric d and the right Haar measure ρ, which is of exponential growth at infinity. In this paper, for any linear operator T on (S,d,ρ) associated with a kernel K satisfying certain integral size condition and H?rmander’s condition, the authors prove that the following four statements regarding the corresponding maximal singular integral T ^∗ are equivalent: T ^∗ is bounded from L_c^￥L_{c}^{\infty} to BMO, T ^∗ is bounded on L ^p for all p∈(1,∞), T ^∗ is bounded on L ^p for some p∈(1,∞) and T ^∗ is bounded from L ¹ to L ^1,∞. As applications of these results, for spectral multipliers of a distinguished Laplacian on (S,d,ρ) satisfying certain Mihlin-H?rmander type condition, the authors obtain that their maximal singular integrals are bounded from L_c^￥L_{c}^{\infty} to BMO, from L ¹ to L ^1,∞, and on L ^p for all p∈(1,∞).     

Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.     

The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ ^d , for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that if we retain all the versions of the diagram, without removing any old feature that is now replaced by new features, the expected combinatorial complexity of the resulting overlay does not grow significantly. Specifically, this complexity is O(n ^⌊d/2⌋log n), for d odd, and O(n ^⌊d/2⌋), for d even. The bound is asymptotically tight in the worst case for d even, and we show that this is also the case for d=3. Several implications of this bound, mainly its relation to approximate halfspace range counting, are also discussed.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.     

On the number of minimal 1-Steiner trees

We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to ann-point set ind-dimensional space, by relating it to a family of convex decompositions of space. TheO(n ^d log^{2d 2}−d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor. The research of D. Eppstein was performed in part while visiting Xerox PARC.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.