Intersection of independent regenerative sets

We investigate the nature of the intersection of two independent regenerative sets. The approach combines Bochners subordination and potential theory for a pair of Markov processes in duality. Received: 21 November 1997 / Revised version: 31 August 1998     

Some properties of the range of super-Brownian motion

We consider a super-Brownian motion X. Its canonical measures can be studied through the path-valued process called the Brownian snake. We obtain the limiting behavior of the volume of the ɛ-neighborhood for the range of the Brownian snake, and as a consequence we derive the analogous result for the range of super-Brownian motion and for the support of the integrated super-Brownian excursion. Then we prove the support of X _t is capacity-equivalent to [0, 1]² in ℝ^d, d≥ 3, and the range of X, as well as the support of the integrated super-Brownian excursion are capacity-equivalent to [0, 1]⁴ in ℝ^d, d≥ 5. Received: 7 April 1998 / Revised version: 2 October 1998     

The fluctuations of the overlap in the Hopfield model with finitely many patterns at the critical temperature

We investigate the limiting fluctuations of the order parameter in the Hopfield model of spin glasses and neural networks with finitely many patterns at the critical temperature 1/β _c = 1. At the critical temperature, the measure-valued random variables given by the distribution of the appropriately scaled order parameter under the Gibbs measure converge weakly towards a random measure which is non-Gaussian in the sense that it is not given by a Dirac measure concentrated in a Gaussian distribution. This remains true in the case of β = β _N →β _c = 1 as N→∞ provided β _N converges to β _c = 1 fast enough, i.e., at speed ?(1/). The limiting distribution is explicitly given by its (random) density. Received: 12 May 1998 / Revised version: 14 October 1998     

Convergence Acceleration of Taylor Sections by Convolution

Taylor sections S _n (f) of an entire function f often provide easy computable polynomial approximants of f . However, while the rate of convergence of (S _n (f)) _n is nearly optimal on circles around the origin, this is no longer true for other plane sets as, for example, real compact intervals. The aim of this paper is to construct for certain families of (entire) functions sequences of polynomial approximants which are computable with essentially the same effort as Taylor sections and which have a better rate of convergence on some parts of the plane. The resulting method may be applied, for example, to (modified) Bessel functions, to confluent hypergeometric functions, or to parabolic cylinder functions. October 2, 1997. Date revised: March 12, 1998. Date accepted: April 28, 1998.     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

NOTE – On the Membership Problem for the Elementary Closure of a Polyhedron

A , an integral vector b and some rational vector , decide whether is outside the elementary closure , is NP-complete. This result is achieved by an extension of a result by Caprara and Fischetti. Received: November 11, 1998     

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck. Received: July 8, 1996     

On the Support Size of Null Designs of Finite Ranked Posets

t -designs of the lattice of subspaces of a vector space over a finite field. The lower bound we find gives the tight bound for many important posets including the Boolean algebra, the lattice of subspaces of a vector space over a finite field, whereas the idea of the proofs of the main theorems makes it possible to prove that the lower bounds in the main theorems are not tight for some posets. Received: November 7, 1995     

Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks

n -vertex edge coloured graphs with multiplicity of Jordan blocks bounded by k can be done in time . Received: November 29, 1994     

Construction of universal modal worlds based on hyperset theory

Knowledge modal formulas are interpreted by a universal modal world in the hypersets universe [A]. This remedies the limitation of the interpretation of knowledge formulas by a tower of modal worlds in the well founded universe [F], where each world can interpret only a portion of knowledge modal formulas. Received: 21 August 1995