The complexity of partial match retrieval in a dynamic setting

The partial match retrieval problem analyzed in this paper is described as follows. Given a positive integer d, a record having d binary attributes consists of a d dimensional binary vector, referred to as the record's key, and a quantity which lies in a commutative semigroup, referred to as the value of the record. Given a set of such records having distinct keys, a partial match query is a request for the sum of the values of all records in the set whose keys lie in a hyperrectangle specified by the query. We consider the problem of designing data structures which permit insertions and deletions of records, and partial match queries. Among our results is the following. There exist data structures which accommodate arbitrary sequences of N manipulations (insertions, deletions, and queries) in (worst case) time approximately (1.226)^dN. Moreover, relative to an appropriate model of computation, this complexity is best possible.     

Large deviations for a symmetric branching random walk on a multidimensional lattice

An important role in the theory of branching random walks is played by the problem of the spectrum of a bounded symmetric operator, the generator of a random walk on a multidimensional integer lattice, with a one-point potential. We consider operators with potentials of a more general form that take nonzero values on a finite set of points of the integer lattice. The resolvent analysis of such operators has allowed us to study branching random walks with large deviations. We prove limit theorems on the asymptotic behavior of the Green function of transition probabilities. Special attention is paid to the case when the spectrum of the evolution operator of the mean numbers of particles contains a single eigenvalue. The results obtained extend the earlier studies in this field in such directions as the concept of a reaction front and the structure of a population inside a front and near its boundary.     

Estimating the covariance matrix and the generalized variance under a symmetric loss

For estimating the power of a generalized variance under a multivariate normal distribution with unknown means, the inadmissibility of the best affine equivariant estimator relative to the symmetric loss is shown, and a class of improved estimators is given. The problem of estimating the covariance matrix is also discussed.     

Boundary value problem for a multidimensional fractional partial differential equation

We construct a fundamental solution of a linear fractional partial differential equation. For an equation with Dzhrbashyan-Nersesyan fractional differentiation operators, we solve a boundary value problem and find a closed-form representation for its solution. The corresponding results for equations with Riemann-Liouville and Caputo derivatives are special cases of the assertions proved here.     

Scattering problem for a multidimensional system of first-order partial differential equations

We construct transformation operators, which enables us to study a scattering problem and investigate the properties of a scattering operator for a multidimensional system of first-order partial differential equations. Institute of Mathematics, Ukrainian Academy of Sciences, Kiev; Zhitomir Pedagogical Institute, Zhitomir. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 8, pp. 1065–1076, August, 1999.     

Solutions of multidimensional partial differential equations representable as a one-dimensional flow

We propose an algorithm for reducing an (M+1)-dimensional nonlinear partial differential equation (PDE) representable in the form of a one-dimensional flow u_t + $w_{x_1 } $ (u, u_x u_xx,…) = 0 (where w is an arbitrary local function of u and its xi derivatives, i = 1,…, M) to a family of M-dimensional nonlinear PDEs F(u,w) = 0, where F is a general (or particular) solution of a certain second-order two-dimensional nonlinear PDE. In particular, the M-dimensional PDE might turn out to be an ordinary differential equation, which can be integrated in some cases to obtain explicit solutions of the original (M+1)-dimensional equation. Moreover, a spectral parameter can be introduced in the function F, which leads to a linear spectral equation associated with the original equation. We present simplest examples of nonlinear PDEs together with their explicit solutions.     

Clustering behavior of finite variance partial sum processes

Summary Clustering rates in Strassen's functional law of the iterated logarithm are determined for finite variance partial sum processes in one dimension. A general characterization of these rates, similar to one recently obtained for onedimensional Brownian motion, shows that relatively mild moment conditions on a partial sum process lead to high order clustering rates at certain points of the Strassen set.Supported in part by NSF Grant DMS-92-07248     

Estimates for the closeness of successive convolutions of multidimensional symmetric distributions

Summary Let ξ₁, ξ₂,... be i.i.d random vectors in ℝ ^k with a common distribution ℒ(ξ_i),... = F, i = 1, 2,.... Let S _n = ξ₁+...+ξ _n . We investigate how small is the difference between ℒ(S _n ) and ℒ(S _{n+ m} ) in the case when ξ _i have symmetric distributions.     

Stability estimate for a multidimensional inverse spectral problem with partial spectral data

In Bellassoued, Choulli and Yamamoto (2009) [4] we proved a log-log type stability estimate for a multidimensional inverse spectral problem with partial spectral data for a Schrödinger operator, provided that the potential is known in a small neighbourhood of the boundary of the domain. In the present paper we discuss the same inverse problem. We show a log type stability estimate under an additional condition on potentials in terms of their X-ray transform. In proving our result, we follow the same method as in Alessandrini and Sylvester (1990) [1] and Bellassoued, Choulli and Yamamoto (2009) [4]. That is we relate the stability estimate for our inverse spectral problem to a stability estimate for an inverse problem consisting in the determination of the potential in a wave equation from a local Dirichlet to Neumann map (DN map in short).     

On the non-existence of a class of symmetric group divisible partial designs

Many non-existence theorems are known for symmetric group divisible partial designs. In the case that these partial designs are auto-dual with ₁=0, an ideal incidence structure can be defined whose elements are the equivalence-classes of non-collinear points and parallel blocks. Except for some trivial cases this incidence structure turns out to be a symmetric design, and by studying its existence we can prove much more powerful non-existence theorems.     

Determination of the partial positivity of the curvature in symmetric spaces

This paper is devoted to the study of the partial positivity (resp. negativity) of the curvature of irreducible symmetric spaces of the classical types. A Riemannian manifoldM is called to have s-positive (resp. s-negative) curvatureif for each x M and for any (s+1)orthonormal vectors {e₁, ..., e_{(s + 1)}}of a tangent space at x, (resp.< ) 0} $$ " align="middle" border="0"> > (resp. <)0,where K(e₁, e_i)denotes the sectional curvature of the linear span of e₁and e_i.If M is an irreducible symmetric space of the compact (resp. noncompact) type, then there exists the smallest integer s, 1 s >(resp. <) 0,since M has nonnegative (resp. nonpositive) sectional curvature and positive (resp. negative) Ricci curvature. Here, we compute this integer s for all the irreducible classical symmetric spaces of the compact (resp. noncompact) type. In general, knowing this s leads to important geometric as well as purely topological consequences.     

Solution of a multidimensional Abel integral equation of the second kind with partial fractional integrals

We construct an explicit representation of the solution of a multidimensional Abel integral equation of the second kind with partial fractional integrals in terms of the Wright function.     

Galerkin finite element approximation of symmetric space-fractional partial differential equations

In this paper, symmetric space-fractional partial differential equations (SSFPDE) with the Riesz fractional operator are considered. The SSFPDE is obtained from the standard advection-dispersion equation by replacing the first-order and second-order space derivatives with the Riesz fractional derivatives of order 2β ∈ (0, 1) and 2α ∈ (1, 2], respectively. We prove that the variational solution of the SSFPDE exists and is unique. Using the Galerkin finite element method and a backward difference technique, a fully discrete approximating system is obtained, which has a unique solution according to the Lax-Milgram theorem. The stability and convergence of the fully discrete schemes are derived. Finally, some numerical experiments are given to confirm our theoretical analysis.     

On completions of symmetric and antisymmetric block diagonal partial matrices

A partial matrix is a matrix where only some of the entries are given. We determine the maximum rank of the symmetric completions of a symmetric partial matrix where only the diagonal blocks are given and the minimum rank and the maximum rank of the antisymmetric completions of an antisymmetric partial matrix where only the diagonal blocks are given.     

The asymptotic variance of a time average in a birth-death process

The variance of a time average is important for planning, running and interpreting experiments. This paper derives a simple method to find this variance for the case of a Markov process. This method is then applied to obtain the variance of a time average for the case of a birth-death process.