Variance estimation for sample quantiles using them out ofn bootstrap

We consider the problem of estimating the variance of a sample quantile calculated from a random sample of sizen. Ther-th-order kernel-smoothed bootstrap estimator is known to yield an impressively small relative error of orderO(n ^−r/(2r+1) ). It nevertheless requires strong smoothness conditions on the underlying density function, and has a performance very sensitive to the precise choice of the bandwidth. The unsmoothed bootstrap has a poorer relative error of orderO(n ^−1/4), but works for less smooth density functions. We investigate a modified form of the bootstrap, known as them out ofn bootstrap, and show that it yields a relative error of order smaller thanO(n ^−1/4) under the same smoothness conditions required by the conventional unsmoothed bootstrap on the density function, provided that the bootstrap sample sizem is of an appropriate order. The estimator permits exact, simulation-free, computation and has accuracy fairly insensitive to the precise choice ofm. A simulation study is reported to provide empirical comparison of the various methods. Supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. HKU 7131/00P).     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Analytic proof of the partition identity A 5,3,3(n)=B 5,3,3 0 (n)

In this paper we give an analytic proof of the identity A _5,3,3(n)=B _5,3,3⁰(n), where A _5,3,3(n) counts the number of partitions of n subject to certain restrictions on their parts, and B _5,3,3⁰(n) counts the number of partitions of n subject to certain other restrictions on their parts, both too long to be stated in the abstract. Our proof establishes actually a refinement of that partition identity. The original identity was first discovered by the first author jointly with M. Ruby Salestina and S.R. Sudarshan in [Proceedings of the International Conference on Analytic Number Theory with Special Emphasis on L-functions, Ramanujan Math. Soc., Mysore, 2005, pp. 57–70], where it was also given a combinatorial proof, thus answering a question of Andrews. Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”     

Self-concordant barriers for hyperbolic means

The geometric mean and the function (det(·)) ^1/m (on the m-by-m positive definite matrices) are examples of “hyperbolic means”: functions of the form p ^1/m , where p is a hyperbolic polynomial of degree m. (A homogeneous polynomial p is “hyperbolic” with respect to a vector d if the polynomial t↦p(x+td) has only real roots for every vector x.) Any hyperbolic mean is positively homogeneous and concave (on a suitable domain): we present a self-concordant barrier for its hypograph, with barrier parameter O(m ²). Our approach is direct, and shows, for example, that the function −mlog(det(·)−1) is an m ²-self-concordant barrier on a natural domain. Such barriers suggest novel interior point approaches to convex programs involving hyperbolic means. Received: December 2, 1999 / Accepted: February 2001?Published online September 3, 2001     

A direct proof for lower semicontinuity of polyconvex functionals

Lower semicontinuity for polyconvex functionals of the form ∫_Ω g(detDu)dx with respect to sequences of functions fromW ^1,n (Ω;ℝ ⁿ ) which converge inL ¹ (Ωℝ ⁿ ) and are uniformly bounded inW ^1,n−1 (Ω;ℝ ⁿ ), is proved. This was first established in [5] using results from [1] on Cartesian Currents. We give a simple direct proof which does not involve currents. We also show how the method extends to prove natural, essentially optimal, generalizations of these results. Supported by MURST, Gruppo Nazionale 40% Partially supported by Australian Research Council     

The Coulomb energy of spherical designs on <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript>

In this work we give upper bounds for the Coulomb energy of a sequence of well separated spherical n-designs, where a spherical n-design is a set of m points on the unit sphere S ² ⊂ ℝ³ that gives an equal weight cubature rule (or equal weight numerical integration rule) on S ² which is exact for spherical polynomials of degree ⩽ n. (A sequence Ξ of m-point spherical n-designs X on S ² is said to be well separated if there exists a constant λ > 0 such that for each m-point spherical n-design X ∈ Ξ the minimum spherical distance between points is bounded from below by .) In particular, if the sequence of well separated spherical designs is such that m and n are related by m = O(n ²), then the Coulomb energy of each m-point spherical n-design has an upper bound with the same first term and a second term of the same order as the bounds for the minimum energy of point sets on S ². Dedicated to Edward B. Saff on the occasion of his 60th birthday.     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Finding shortest paths in the plane in the presence of barriers to travel (for any lp - norm)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that when distances are measured by an 1_p - norm with 1 < p < ∞, these paths are formed by sequences straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in O(n² log n) time. If the total number of edges in this network is e (bounded by n²), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If the origins, shortest paths from all origins to all destinations can thus be found in O(ne log n) ≤ O(n^{3 log n}) time.It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. l_p-norm with p = 1 or p = ∞) can be deduced from the results of the algorithm.     

H m -modified wave operator for nonlinear Hartree equation in space of dimensionn≥2

We consider the scattering problem for the Hartree equation with potential |x|⁻¹ in a space of dimensionn≥2. We prove the existence ofH ^m -modified wave operator for Hartree equation on a dense set of a neighborhood of zero inH ^m (ℝ ⁿ ), meanwhile, we obtain also the global existence for the Cauchy problem of Hartree equation in a space of dimensionn≥2. This project is supported by the National Natural Science Foundation of China, 19601005     

Quadratic forms between euclidean spheres

We study the relationship between the dimensions of euclidean spheres which admit a nonconstant homogeneous quadratic map between them. Givenm (respectivelyn), we determine the least (respectively greatest) possible value ofn (respectivelym) for which there exists a nonconstant homogeneous quadratic mapS ^m →S ⁿ . Research partially supported by NSF DMS-9201204     

Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem

In this paper we propose a weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, we only use full-Newton step. Finally, the currently best known iteration bound for the algorithm with a small-update method, namely, O(√nlog n/ε) is derived, which is as good as the bound for the linear optimization analogue.     

Polynomial Root-Finding Methods Whose Basins of Attraction Approximate Voronoi Diagram

Given a complex polynomial p(z) with at least three distinct roots, we first prove that no rational iteration function exists where the basin of attraction of a root coincides with its Voronoi cell. In spite of this negative result, we prove that the Voronoi diagram of the roots can be well approximated through a high order sequence of iteration functions, the Basic Family, B _m (z), m≥2. Let θ be a simple root of p(z), V(θ) its Voronoi cell, and A _m (θ) its basin of attraction with respect to B _m (z). We prove that given any closed subset C of V(θ), including any homothetic copy of V(θ), there exists m ₀ such that for all m≥m ₀, C is also a subset of A _m (θ). This implies that when all roots of p(z) are simple, the basins of attraction of B _m (z) uniformly approximate the Voronoi diagram of the roots to within any prescribed tolerance. Equivalently, the Julia set of B _m (z), and hence the chaotic behavior of its iterations, will uniformly lie to within prescribed strip neighborhood of the boundary of the Voronoi diagram. In a sense, this is the strongest property a rational iteration function can exhibit for polynomials. Next, we use the results to define and prove an infinite layering within each Voronoi cell of a given set of points, whether known implicitly as roots of a polynomial equation, or explicitly via their coordinates. We discuss potential application of our layering in computational geometry.     

Equidistant frequency permutation arrays and related constant composition codes

In this paper we study the special class of equidistant constant composition codes of type CCC(n, d, μ ^m ) (where n = m μ), which correspond to equidistant frequency permutation arrays; we also consider related codes with composition “close to” μ ^m . We establish various properties of these objects and give constructions for optimal families of codes.     

On the Riesz means of coefficients of <Emphasis Type="Italic">m</Emphasis>th symmetric power <Emphasis Type="Italic">L</Emphasis>-functions

Let c _n be the Fourier coefficients of L(sym ^m   f, s), and Δρ(x; sym ^m   f) be the error term in the asymptotic formula for ∑ _n≪x c _n . In this paper, we study the Riesz means of Δρ(x; sym ^m   f) and obtain a truncated Voronoi-type formula under the hypothesis Nice(m, f).     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

Sign changes in rational L w 1 -approximation

Let f ∈ L _w ¹ [−1, 1], let r _n,m(f) be the best rational L _w ¹ -approximation for f with respect to real rational functions of degree at most n in the numerator and of degree at most m in the denominator, let m = m(n), and let lim _{n → ∞} (n-m(n)) = ∞. In this case, we show that the counting measures of certain subsets of sign changes of f-r _n,m (f) converge weakly to the equilibrium measure on [−1, 1] as n → ∞. Moreover, we prove estimates for discrepancy between these counting measures and the equilibrium measure. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 283–287, February, 2006.     

A proof of Selberg's orthogonality for automorphic L-functions

Let π and π′ be automorphic irreducible cuspidal representations of GL_m(Q_A) and GL_m′(Q_A), respectively. Assume that π and π′ are unitary and at least one of them is self-contragredient. In this article we will give an unconditional proof of an orthogonality for π and π′, weighted by the von Mangoldt function Λ(n) and 1−n/x. We then remove the weighting factor 1−n/x and prove the Selberg orthogonality conjecture for automorphic L-functions L(s,π) and L(s,π′), unconditionally for m≤4 and m′≤4, and under the Hypothesis H of Rudnick and Sarnak [20] in other cases. This proof of Selberg's orthogonality removes such an assumption in the computation of superposition distribution of normalized nontrivial zeros of distinct automorphic L-functions by Liu and Ye [12].