The Parallel Simplicity of Compaction and Chaining

Given a set of values x₁, x₂,..., x_n, of which k are nonzero, the compaction problem is the problem of moving the nonzero elements into the first k consecutive memory locations. The chaining problem asks that the nonzero elements be put into a linked list. One can in addition require that the elements remain in the same order, leading to the problems of ordered compaction and ordered chaining, respectively. This paper introduces a technique involving perfect hash functions that leads to a deterministic algorithm for ordered compaction running on a CRCW PRAM in time O(log k/log log n) using n processors. A matching lower bound for unordered compaction is given. The ordered chaining problem is shown to be solvable in time O(α(k)) with n processors (where α is a functional inverse of Ackermann′s function) and unordered chaining is shown to he solvable in constant time with n processors when k < n^{1/4− ε}.     

The Complexity of Two-Point Boundary-Value Problems with Piecewise Analytic Data

Previous work on the ε-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the ε-complexity is proportional to ln (ε⁻¹), and there is a finite element p-method (in the sense of Babu ka) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ε < √2. If we know only that there are b ≥ 2 breakpoints, but we de not know their location, then the ε-complexity is proportional to bε⁻¹, and a finite element h-method is nearly optimal. In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L₂ sense.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

The complexity of finding generalized paths in tournaments

Given a tournament with n vertices, we consider the number of comparisons needed, in the worst case, to find a permutation υ₁υ₂…υ_n of the vertices, such that the results of the games υ₁υ₂, υ₂υ₃,…, υ_n−1υ_n match a prescribed pattern. If the pattern requires all arcs to go forwrd, i.e., υ₁ → υ₂, υ₂ → υ₃,…, υ_n−1 → υ_n, and the tournament is transitive, then this is essentially the problem of sorting a linearly ordered set. It is well known that the number of comparisons required in this case is at least cn lg n, and we make the observation that O(n lg n) comparisons suffice to find such a path in any (not necessarily transitive) tournament. On the other hand, the pattern requiring the arcs to alternate backward-forward-backward, etc., admits an algorithm for which O(n) comparisons always suffice. Our main result is the somewhat surprising fact that for various other patterns the complexity (number of comparisons) of finding paths matching the pattern can be cn lg^αn for any α between 0 and 1. Thus there is a veritable spectrum of complexities, depending on the prescribed pattern of the desired path. Similar problems on complexities of algorithms for finding Hamiltonian cycles in graphs and directed graphs have been considered by various authors, [2, pp. 142, 148, 149; 4].     

Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

Rank One Perturbations with Infinitesimal Coupling

We consider a positive self-adjoint operator A and formal rank one perturbations B = A + α(φ, ·)φ, where φ ₋₂(A) but φ ₋₁ (A), with _s(A) the usual scale of spaces. We show that B can be defined for such φ and what are essentially negative infinitesimal values of α. In a sense we will make precise, every rank one perturbation is one of three forms: (i) φ ₋₁(A), α ; (ii) φ ₋₁, α = ∞; or (iii) the new type we consider here.     

On an infinite series of Abel occurring in the theory of interpolation

The purpose of this paper is to show that for a certain class of functions f which are analytic in the complex plane possibly minus (−∞, −1], the Abel series f(0) + Σ_{n = 1}^∞ f⁽ⁿ⁾(nβ) z(z − nβ)^{n − 1}/n! is convergent for all β>0. Its sum is an entire function of exponential type and can be evaluated in terms of f. Furthermore, it is shown that the Abel series of f for small β>0 approximates f uniformly in half-planes of the form Re(z) − 1 + δ, δ>0. At the end of the paper some special cases are discussed.     

On piecewise-polynomial approximation of functions with a bounded fractional derivative in an Lp-norm

We study the error in approximating functions with a bounded (r + α)th derivative in an L_p-norm. Here r is a nonnegative integer, α ε [0, 1), and ƒ^{(r + α)} is the classical fractional derivative, i.e., ƒ^{(r + α)}(y) = ∝₀¹, ^α d(ƒ^(r)(t)). We prove that, for any such function ƒ, there exists a piecewise-polynomial of degree s that interpolates ƒ at n equally spaced points and that approximates ƒ with an error (in sup-norm) ƒ^{(r + α)}_p O(n^{−(r+α−1/p}). We also prove that no algorithm based on n function and/or derivative values of ƒ has the error equal ƒ^{(r + α)}_p O(n^{−(r+α−1/p}) for any ƒ. This implies the optimality of piecewise-polynomial interpolation. These two results generalize well-known results on approximating functions with bounded rth derivative (α = 0). We stress that the piecewise-polynomial approximation does not depend on α nor on p. It does not depend on the exact value of r as well; what matters is an upper bound s on r, s r. Hence, even without knowing the actual regularity (r, α, and p) of ƒ, we can approximate the function ƒ with an error equal (modulo a constant) to the minimal worst case error when the regularity were known.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

Nonnegative solutions of a nonlinear recurrence

Orthonormal polynomials with weight ¦τ¦ exp(−τ⁴) have leading coefficients with recurrence properties which motivate the more general equations ξ_m(ξ_{m − 1} + ξ_m + ξ_{m + 1}) = γ_m², M = 1, 2,…, where ξ_o is a fixed nonnegative value and γ₁, γ₂,… are positive constants. For this broader problem, the existence of a nonnegative solution is proved and criteria are found for its uniqueness. Then, for the motivating problem, an asymptotic expansion of its unique nonnegative solution is obtained and a fast computational algorithm, with error estimates, is given.     

Zeros of orthogonal polynomials on the real line

Let p_n(x) be the orthonormal polynomials associated to a measure dμ of compact support in . If Esupp(dμ), we show there is a δ>0 so that for all n, either p_n or p_n+1 has no zeros in (E−δ,E+δ). If E is an isolated point of supp(μ), we show there is a δ so that for all n, either p_n or p_n+1 has at most one zero in (E−δ,E+δ). We provide an example where the zeros of p_n are dense in a gap of supp(dμ).     

On the Erd s-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings

A link between Ramsey numbers for stars and matchings and the Erd s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K_2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K_1,m in K_2m−1 with edges e₁, e₂,…, e_m such that c(e₁)+c(e₂)++c(e_m)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(K^r_(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z₁, Z₂,…, Z_m of S such that c(Z₁)+c(Z₂)++c(Z_m)≡0 (mod m).     

Complete on Average Boolean Satisfiability

We present in this paper a dynamic binary coding scheme α on CNF formulas ψ, and show that under a uniform distribution μ_α on binary string α(ψ), SAT is complete on average, where μ_α(ψ) is proportional to α(ψ)⁻²2^−α(ψ). We then show that there is k₀>2 such that for all kk₀, kSAT under μ_α is complete on average.     

Tractability of Multivariate Integration for Weighted Korobov Classes

We study the worst-case error of multivariate integration in weighted Korobov classes of periodic functions of d coordinates. This class is defined in terms of weights γ_j which moderate the behavior of functions with respect to successive coordinates. We study two classes of quadrature rules. They are quasi-Monte Carlo rules which use n function values and in which all quadrature weights are 1/n and rules for which all quadrature weights are non-negative. Tractability for these two classes of quadrature rules means that the minimal number of function values needed to guarantee error in the worst-case setting is bounded by a polynomial in d and ⁻¹. Strong tractability means that the bound does not depend on d and depends polynomially on ⁻¹. We prove that strong tractability holds iff ∑^∞_j=1 γ_j<∞, and tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/log d<∞. Furthermore, strong tractability or tractability results are achieved by the relatively small class of lattice rules. We also prove that if ∑^∞_j=1 γ^1/α_j<∞, where α measures the decay of Fourier coefficients in the weighted Korobov class, then for d1, n prime and δ>0 there exist lattice rules that satisfy an error bound independent of d and of order n^−α/2+δ. This is almost the best possible result, since the order n^−α/2 cannot be improved upon even for d=1. A corresponding result is deduced for weighted non-periodic Sobolev spaces: if ∑^∞_j=1 γ^1/2_j<∞, then for d1, n prime and δ>0 there exist shifted lattice rules that satisfy an error bound independent of d and of order n^−1+δ. We also check how the randomized error of the (classical) Monte Carlo algorithm depends on d for weighted Korobov classes. It turns out that Monte Carlo is strongly tractable iff ∑^∞_j=1 log γ_j<∞ and tractable iff lim sup_d→∞ ∑^d_j=1 log γ_j/log d<∞. Hence, in particular, for γ_j=1 we have the usual Korobov space in which integration is intractable for the two classes of quadrature rules in the worst-case setting, whereas Monte Carlo is strongly tractable in the randomized setting.     

Minimax estimation of the mean of spherically symmetric distributions under general quadratic loss

For X one observation on a p-dimensional (p ≥ 4) spherically symmetric (s.s.) distribution about θ, minimax estimators whose risks dominate the risk of X (the best invariant procedure) are found with respect to general quadratic loss, L(δ, θ) = (δ − θ)′ D(δ − θ) where D is a known p × p positive definite matrix. For C a p × p known positive definite matrix, conditions are given under which estimators of the form δ_a,r,C,D(X) = (I − (ar(|X|²)) D^−1/2CD^1/2 |X|⁻²)X are minimax with smaller risk than X. For the problem of estimating the mean when n observations X₁, X₂, …, X_n are taken on a p-dimensional s.s. distribution about θ, any spherically symmetric translation invariant estimator, δ(X₁, X₂, …, X_n), with have a s.s. distribution about θ. Among the estimators which have these properties are best invariant estimators, sample means and maximum likelihood estimators. Moreover, under certain conditions, improved robust estimators can be found.     

Polynomial Projections inC[−1, 1] andL(−1, 1) with Growthn, 0<γ1/2

Forγ(0, 1/2] we constructn-dimensional polynomial subspacesY_nofC[−1, 1] andL¹(−1, 1) such that the relative projection constantsλ(Y_n, C[−1, 1]) andλ(Y_n, L¹(−1, 1)) grow asn^γ. These subspaces are spanned by Chebyshev polynomials of the first and second kind, respectively. The spacesL¹_{w(α, β}wherew_{α, β}is the weight function of the Jacobi polynomials and (α, β){(−1/2, −1/2), (−1/2, 0), (0, −1/2)} are also studied.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

Extremal problems concerning Kneser graphs

Let and be two intersecting families of k-subsets of an n-element set. It is proven that | | ≤ (_k−1ⁿ⁻¹) + (_k−1ⁿ⁻¹) holds for , and equality holds only if there exist two points a, b such that {a, b} ∩ F ≠ for all F . For an example showing that in this case max | | = (1−o(1))(_kⁿ) is given. This disproves an old conjecture of Erdös [7]. In the second part we deal with several generalizations of Kneser's conjecture.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.