Two-sided bounds and leading term for rates of convergence in the multivariate central limit theorem

For a sequence of independent and identically distributed random vectors, upper and lower bounds are obtained for the discrepancy between the probability measure P_n, induced by their normalized sum, and the Normal measure Φ. The upper and lower bounds are of the same order of magnitude. These results may be derived by a “leading term” approach, in which a signed measure Q_n is introduced as a first order approximation to P_n − Φ. The purpose of this paper is to investigate properties of the leading term.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

Estimates of Freud-Christoffel functions for some weights with the whole real line as support

Upper and lower bounds for generalized Christoffel functions, called Freud-Christoffel functions, are obtained. These have the form λ_n,p(W,j,x) = infPW_Lp(R)/|P^(j)(X)| where the infimum is taken over all polynomials P(x) of degree at most n − 1. The upper and lower bounds for λ_n,p(W,j,x) are obtained for all 0 < p ∞ and J = 0, 1, 2, 3,… for weights W(x) = exp(−Q(x)), where, among other things, Q(x) is bounded in [− A, A], and Q″ is continuous in β(−A, A) for some A > 0. For p = ∞, the lower bounds give a simple proof of local and global Markov-Bernstein inequalities. For p = 2, the results remove some restrictions on Q in Freud's work. The weights considered include W(x) = exp(− ¦x¦^α/2), α > 0, and W(x) = exp(− exp(¦x¦)), > 0.     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

Spreading Rumors Rapidly Despite an Adversary

In thecollect problem(M. Saks, N. Shavit, and H. Woll,in“Proceedings of the 2nd ACM–SIAM Symposium on Discrete Algorithms, 1991),nprocessors in a shared-memory system must each learn the values ofnregisters. We give a randomized algorithm that solves the collect problem inO(n log³ n) total read and write operations with high probability, even if timing is under the control of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound ofO(n²) steps and the best previously known bound ofO(n^3/2 log n) steps, and is close to the lower bound of Ω(n log n) steps. Furthermore, we show how this algorithm can be used to obtain a multiuse cooperative collect protocol that isO(log³ n)-competitive in the latency model of Ajtaiet al.(“Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science,” 1994); andO(n^1/2 log^3/2 n)-competitive in the throughput model of Aspnes and Waarts (“Proceedings of the 28th ACM Symposium on Theory of Computing,” 1996). In both cases the competitive ratios are within a polylogarithmic factor of optimal.     

Adjacency preserving bijective maps on triangular matrices over any division ring

Let 𝕋 _n (D) be the set of n × n upper triangular matrices over a division ring D. We characterize the adjacency preserving bijective maps in both directions on 𝕋 _n (D) (n ≥ 3). As applications, we describe the ring semi-automorphisms and the Jordan automorphisms on upper triangular matrices over a simple Artinian ring.     

Sharp inequalities for convolution-type operators

Let μ be a probability measure on [− a, a], a > 0, and let x₀ε[− a, a], f ε Cⁿ([−2a, 2a]), n 0 even. Using moment methods we derive best upper bounds to ¦∫_−a^a ([f(x₀ + y) + f(x₀ − y)]/2) μ(dy) − f(x₀)¦, leading to sharp inequalities that are attainable and involve the second modulus of continuity of f⁽ⁿ⁾ or an upper bound of it.     

Routing Problems on the Mesh of Buses

The mesh of buses (MBUSs) is a parallel computation model which consists ofn×nprocessors,nrow buses, andncolumn buses, but no local connections between neighboring processors. Annlower bound for the permutation routing on this model is shown. The proof does not depend on common predetermined assumptions such as “if a packet has to move horizontally then it has to ride on a horizontal bus at least once.” As for upper bounds, a 1.5nalgorithm is shown.     

Adaptive Semiparametric Estimation of the Memory Parameter

In Giraitis, Robinson, and Samarov (1997), we have shown that the optimal rate for memory parameter estimators in semiparametric long memory models with degree of “local smoothness” β is n^−r(β), r(β)=β/(2β+1), and that a log-periodogram regression estimator (a modified Geweke and Porter-Hudak (1983) estimator) with maximum frequency m=m(β)n^2r(β) is rate optimal. The question which we address in this paper is what is the best obtainable rate when β is unknown, so that estimators cannot depend on β. We obtain a lower bound for the asymptotic quadratic risk of any such adaptive estimator, which turns out to be larger than the optimal nonadaptive rate n^−r(β) by a logarithmic factor. We then consider a modified log-periodogram regression estimator based on tapered data and with a data-dependent maximum frequency m=m(β), which depends on an adaptively chosen estimator β of β, and show, using methods proposed by Lepskii (1990) in another context, that this estimator attains the lower bound up to a logarithmic factor. On one hand, this means that this estimator has nearly optimal rate among all adaptive (free from β) estimators, and, on the other hand, it shows near optimality of our data-dependent choice of the rate of the maximum frequency for the modified log-periodogram regression estimator. The proofs contain results which are also of independent interest: one result shows that data tapering gives a significant improvement in asymptotic properties of covariances of discrete Fourier transforms of long memory time series, while another gives an exponential inequality for the modified log-periodogram regression estimator.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

The Complexity of Indefinite Elliptic Problems with Noisy Data

We study the complexity of second-order indefinite elliptic problems −div(au) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH¹(Ω)-norm. The problem elementsfbelong to the unit ball ofW^{r, p}, (Ω), wherep [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations off,a, orb(or their derivatives). The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the -complexity (minimal cost of calculating an -approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/)^{d/r + s}.     

An application of the Turán theorem to domination in graphs

A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γ_s(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs.     

Approximating Band- and Energy-Limited Signals in the Presence of Jitter

This paper deals with recovering band- and energy-limited signals from a finite set of their perturbed samples taken at slightly wrong points. The perturbations in sample points reading (called jitter) and in the measurements of the corresponding samples are assumed to be bounded byγandδ, respectively. The goal is to analyze how the minimal worst-case recovery error depends onγandδ. This is accomplished by proving tight upper and lower bounds on the diameter of information. The main conclusion is that the jitter causes the error of orderγΔ^3/2+δ, whereΔis the bandwidth.     

On the Rate of Convergence of Two Bernstein–Bézier Type Operators for Bounded Variation Functions

In this paper we study the rate of convergence of two Bernstein–Bézier type operatorsB^(α)_nandL^(α)_nfor bounded variation functions. By means of construction of suitable functions and the method of Bojanic and Vuillemier (J. Approx. Theory31(1981), 67–79), using some results of probability theory, we obtain asymptotically optimal estimations ofB^(α)_nandL^(α)_nfor bounded variation functions at points of continuity and points of discontinuity.     

On the Erd s-diameter of sets

Let δ(n) denote the minimum diameter of a set of n points in the plane in which any two positive distances, if they are different, differ by at least one. Erd s conjectured that for n sufficiently big we have δ(n) = n − 1, the extremal configuration being n equidistant points on a line. In this note we prove an asymptotic version of this conjecture for the special case of sets which lie in a parallel half-strip.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Text Indexing and Dictionary Matching with One Error

The indexing problem is where a text is preprocessed and subsequent queries of the form “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form “Find all occurrences of dictionary patterns in text T” are answered in time proportional to the length of the text and the number of occurrences.There exist efficient worst-case solutions for the indexing problem and the dictionary matching problem, but none that find approximate occurrences of the patterns, i.e., where the pattern is within a bound edit (or Hamming) distance from the appropriate text location.In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem with one error. We preprocess the data in time O(n log² n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the indexing problem is O(m log n log log n + tocc), where m is the query string size and tocc is the number of occurrences. Our query time for the dictionary matching problem is O(n log³ d log log d + tocc), where n is the text size and d the dictionary size. The time bounds above apply to both bounded and unbounded alphabets.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Normal Approximation Rate of the Kernel Smoothing Estimator in a Partial Linear Model

By establishing the asymptotic normality for the kernel smoothing estimatorβ_nof the parametric componentsβin the partial linear modelY=X′β+g(T)+, P. Speckman (1988,J. Roy. Statist. Soc. Ser. B50, 413–456) proved that the usual parametric raten^−1/2is attainable under the usual “optimal” bandwidth choice which permits the achievement of the optimal nonparametric rate for the estimation of the nonparametric componentg. In this paper we investigate the accuracy of the normal approximation forβ_nand find that, contrary to what we might expect, the optimal Berry–Esseen raten^−1/2is not attainable unlessgis undersmoothed, that is, the bandwidth is chosen with faster rate of tending to zero than the “optimal” bandwidth choice.     

A new approach to Euler splines

Starting from the exponential Euler polynomials discussed by Euler in “Institutions Calculi Differentialis,” Vol. II, 1755, the author introduced in “Linear operators and approximation,” Vol. 20, 1972, the so-called exponential Euler splines. Here we describe a new approach to these splines. Let t be a constant such that t=|t|e^iα, −π<α<π,t≠0,t≠1.. Let S₁(x:t) be the cardinal linear spline such that S₁(v:t) = t^v for all v ε Z. Starting from S₁(x:t) it is shown that we obtain all higher degree exponential Euler splines recursively by the averaging operation . Here S_n(x:t) is a cardinal spline of degree n if n is odd, while is a cardinal spline if n is even. It is shown that they have the properties S_n(v:t) = t^v for v ε Z.