Small noise asymptotics for invariant densities for a class of diffusions: A control theoretic view

We consider multi-dimensional nondegenerate diffusions with invariant densities, with the diffusion matrix scaled by a small >0. The o.d.e. limit corresponding to =0 is assumed to have the origin as its unique globally asymptotically stable equilibrium. Using control theoretic methods, we show that in the ↓0 limit, the invariant density has the form ≈exp(−W(x)/²), where the W is characterized as the optimal cost of a deterministic control problem. This generalizes an earlier work of Sheu. Extension to multiple equilibria is also given.     

On the reducibility of a class of nonlinear quasi-periodic system with small perturbation parameter near zero equilibrium point

This work focuses on the reducibility of the following real nonlinear analytical quasiperiodic system:

where A is a real 2×2 constant matrix, and f(t,0,)=O() and ∂_xf(t,0,)=O() as →0. With some non-resonant conditions of the frequencies with the eigenvalues of A and without any nondegeneracy condition with respect to , by an affine analytic quasiperiodic transformation we change the system to a suitable norm form at the zero equilibrium for most of the sufficiently small perturbation parameter .     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.     

A derivative free iterative method for finding multiple roots of nonlinear equations

For an equation f(x)=0 having a multiple root of multiplicity m>1 unknown, we propose a transformation which converts the multiple root to a simple root of H(x)=0. The transformed function H(x) of f(x) with a small >0 has appropriate properties in applying a derivative free iterative method to find the root. Moreover, there is no need to choose a proper initial approximation. We show that the proposed method is superior to the existing methods by several numerical examples.     

Existence and selection of steady bubbles in a Hele–Shaw cell

This paper concerns the existence of a steadily translating bubble in a Hele–Shaw cell for small but non-zero surface tension ². We rigorously conclude that for bubble velocity U relative to the fluid velocity at infinity in the interval (1,2), analytic symmetric solutions exist in the asymptotic limit of surface tension ²→0 if and only if the Stokes constant for a relatively simple nonlinear differential equation is zero. This Stokes constant S depends on the parameter α(0,1) corresponding to bubble size and . Earlier calculations have shown S to be zero for a discrete set of values of a.     

Succinct data structures for flexible text retrieval systems

We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf*idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf*idf scores there has been no efficient data structures for arbitrary patterns.Our new data structures support these queries using small space. The space is only 2/ times the size of compressed documents plus 10n bits for a document collection of length n, for any 0<1. This is much smaller than the previous O(nlogn) bit data structures. Query time is O(m+qlogn) for listing and computing tf*idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

Optimization of a convex program with a polynomial perturbation

We consider the problem of minimizing a convex function plus a polynomial p over a convex body K. We give an algorithm that outputs a solution x whose value is within range_K(p) of the optimum value, where range_K(p)=sup_xKp(x)−inf_xKp(x). When p depends only on a constant number of variables, the algorithm runs in time polynomial in 1/, the degree of p, the time to round K and the time to solve the convex program that results by setting p=0.     

Galerkin solution of a singular integral equation with constant coefficients

Galerkin methods are used to approximate the singular integral equation

with solution φ having weak singularity at the endpoint −1, where a, b≠0 are constants. In this case φ is decomposed as φ(x)=(1−x)^α(1+x)^βu(x), where β=−α, 0<α<1. Jacobi polynomials are used in the discussions. Under the conditions fH^μ[−1,1] and k(t,x)H^μ,μ[−1,1]×[−1,1], 0<μ<1, the error estimate under a weighted L² norm is O(n^−μ). Under the strengthened conditions f^″H^μ[−1,1] and , 2α−<μ<1, the error estimate under maximum norm is proved to be O(n^2α−−μ+), where , >0 is a small enough constant.     

A parallel extended GCD algorithm

A new parallel extended GCD algorithm is proposed. It matches the best existing parallel integer GCD algorithms of Sorenson and Chor and Goldreich, since it can be achieved in O(n/logn) time using at most n¹⁺ processors on CRCW PRAM. Sorenson and Chor and Goldreich both use a modular approach which consider the least significant bits. By contrast, our algorithm only deals with the leading bits of the integers u and v, with uv. This approach is more suitable for extended GCD algorithms since the coefficients of the extended version a and b, such that au+bv=gcd(u,v), are deeply linked with the order of magnitude of the rational v/u and its continuants. Consequently, the computation of such coefficients is much easier.     

Density and invariant means in left amenable semigroups

A left cancellative and left amenable semigroup S satisfies the Strong Følner Condition. That is, given any finite subset H of S and any >0, there is a finite nonempty subset F of S such that for each sH, |sFF|<|F|. This condition is useful in defining a very well behaved notion of density, which we call Følner density, via the notion of a left Følner net, that is a net F_ααD of finite nonempty subsets of S such that for each sS, (|sF_αF_α|)/|F_α| converges to 0. Motivated by a desire to show that this density behaves as it should on cartesian products, we were led to consider the set LIM₀(S) which is the set of left invariant means which are weak^* limits in l_∞(S)^* of left Følner nets. We show that the set of all left invariant means is the weak^* closure of the convex hull of LIM₀(S). (If S is a left amenable group, this is a relatively old result of C. Chou.) We obtain our desired density result as a corollary. We also show that the set of left invariant means on is actually equal to . We also derive some properties of the extreme points of the set of left invariant means on S, regarded as measures on βS, and investigate the algebraic implications of the assumption that there is a left invariant mean on S which is non-zero on some singleton subset of βS.     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Theorems about the attractor for incompressible non-Newtonian flow driven by external forces that are rapidly oscillating in time but have a smooth average

This paper discusses the incompressible non-Newtonian fluid with rapidly oscillating external forces g(x,t)=g(x,t,t/) possessing the average g⁰(x,t) as →0⁺, where 0<₀<1. Firstly, with assumptions (A₁)–(A₅) on the functions g(x,t,ξ) and g⁰(x,t), we prove that the Hausdorff distance between the uniform attractors and in space H, corresponding to the oscillating equations and the averaged equation, respectively, is less than O() as →0⁺. Then we establish that the Hausdorff distance between the uniform attractors and in space V is also less than O() as →0⁺. Finally, we show for each [0,₀].     

Approximate range searching using binary space partitions

We show how any BSP tree for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(nlogn) such that -approximate range searching queries with any constant-complexity convex query range can be answered in O(min_>0{(1/)+k}logn) time, where k is the number of segments intersecting the -extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves.We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in such that -approximate range searching with any constant-complexity convex query range can be done in O(logn+min_>0{(1/^d−1)+k}) time.     

The maximum asymptotic bias of S-estimates for regression over the neighborhoods defined by certain special capacities

The maximum asymptotic bias of an S-estimate for regression in the linear model is evaluated over the neighborhoods (called (c,γ)-neighborhoods) defined by certain special capacities, and its lower and upper bounds are derived. As special cases, the (c,γ)-neighborhoods include those in terms of -contamination, total variation distance and Rieder's (,δ)-contamination. It is shown that when the model distribution is normal and the (,δ)-contamination neighborhood is adopted, the lower and upper bounds of an S-estimate (including the LMS-estimate) based on a jump function coincide with the maximum asymptotic bias. The tables of the maximum asymptotic bias of the LMS-estimate are given. These results are an extension of the corresponding ones due to Martin et al. (Ann. Statist. 17 (1989) 1608), who used -contamination neighborhoods.     

Stability for parametric implicit vector equilibrium problems

In this paper, we consider a class of parametric implicit vector equilibrium problems in Hausdorff topological vector spaces where a mapping f and a set K are perturbed by parameters and λ, respectively. We establish sufficient conditions for the upper semicontinuity and lower semicontinuity of the solution set mapping S:Λ₁×Λ₂→2^X for such parametric implicit vector equilibrium problems.     

A note on perturbation of non-symmetric Dirichlet forms by signed smooth measures

This article discusses the perturbation of a non-symmetric Dirichlet form,(ε, D(ε)), by a signed smooth measure μ, whereμ=μ1 -μ2 with μ1 and μ2 being smooth measures. It gives a sufficient condition for the perturbed form (εμ, D(εμ)) (for some αo ≥ 0) to be a coercive closed form.     

Independence Distribution Preserving Covariance Structures for the Multivariate Linear Model

Consider the multivariate linear model for the random matrixY_n×pMN(XB, VΣ), whereBis the parameter matrix,Xis a model matrix, not necessarily of full rank, andVΣ is annp×nppositive-definite dispersion matrix. This paper presents sufficient conditions on the positive-definite matrixVsuch that the statistics for testingH₀: CB=0vsH_a: CB≠0have the same distribution as under the i.i.d. covariance structureIΣ.