Search

This paper provides logspace and small circuit depth analogs of the result of Valiant and Vazirani, which is a randomized (or nonuniform) reduction from $NP$ to its arithmetic analog $\plusminus P$. We show a similar randomized reduction between the Boolean classes $NL$ and semiunbounded fan-in Boolean circuits and their arithmetic counterparts. These reductions are based on the Isolation Lemma of Mulmuley, Vazirani and Vazirani. Combinatorically our results can be viewed as simple (logspace) transformations of existential quantifiers into counting quantifiers in graphs and shallow circuits.

In 1962 Posa conjectured that any graph G of order n and minimum degree at least ⅔ n contains the square of a Hamiltonian cycle. In this paper we prove this conjecture for sufficiently large n. © 1996 John Wiley & Sons, Inc.

Let Gmn denote the set of simple graphs with n vertices and m edges, t(G) the number of spanning trees of a graph G, and F ≥ H if t(Ks\E(F)) ≥ t(Ks\E(H)) for every s ≥ max{v(F), v(H)}. We give a complete characterization of ≥-maximal (maximum) graphs in Gmn subject to m ≤ n. This result contains, in particular, a complete characterization of those graphs in Gkn that have the maximum number of spanning trees among all graphs in Gkn subject to n(n − 1)/2 − n ≤ k ≤ n(n − 1)/2. We discuss and use properties of the Laplacian polynomial L(λ, G) of a graph G [8]. Because of relation t(Ks\E(Gn)) = ss-n-2L(s, Gn) [8], the main result of the paper can also be interpreted as a characterisation of those graphs in Gmn, m ≤ n, having the maximum. Laplacian polynomial for every integer λ ≥ n. We also give an overview of some known approaches and results on this problem. © 1996 John Wiley & Sons, Inc.

In this paper, we apply some recent eigenvalue bounds based on heat kernel estimates to provide polynomial bounds on Markov chain approaches to a number of sampling problems. In particular, for the space S of m by n contingency tables (which are arrays of non-negative integers having fixed row and column sums), we give the first bounds on the mixing time for the natural walk on S which is polynomial in m, n and the row and column sums, provided the minimum row and column sums are large enough.

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex xϵ V(H) and deg(x, y) = o(D) for each pair of vertices x, y ϵ V(H), where D infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 − o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via “nibbles.” Further, let Tα be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r · (1 − α)]. We show that almost surely Tα ∼ (1/α)r−1 · n/r(r − 1) as α 0+ holds. © 1996 John Wiley & Sons, Inc.

Raghavan's paper on derandomized approximation algorithms for 0–1 packing integer programs raised two challenging problems [11]: 1. Are there more examples of NP-hard combinatorial optimization problems for which derandomization yields constant factor approximations in polynomial-time ? 2. The pessimistic estimator technique shows an O(mn)-time implementation of the conditional probability method on the RAM model of computation in case of m large deviation events associated to m unweighted sums of n indepependent Bernoulli trials. Is there a fast algorithm also in case of rational weighted sums of Bernoulli trials ?

In this paper we prove improved lower and upper bounds on the size of sample spaces which which are required to be independent on specified neighborhoods. Our new constructions yield sample spaces whose size is smaller than previous constructions due to Schulman. Our lower bounds generalize the known lower bounds of Alon et al. and Chor et al. In obtaining these bounds we examine the possibilities and limitations of amplifying limited independence by fixed functions. We show that in general independence cannot be amplified from k-wise independence to (k + 1)-wise independence. Finally, we enumerate all possible logical consequences of pairwise independence random bits, i.e., events whose probabilities are a consequence of pairwise independence.

The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 – o(1))t/2/log t times a positive constant. Together with the known upper bound of (1 + o(1))t2/log t, it follows that R(3, t) has asymptotic order of magnitude t2/log t. © 1995 John Wiley & Sons, Inc.

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well‐known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd2 log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}n of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log2 d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties. © 1995 Wiley Periodicals, Inc.

Mutafchiev [7] observed that μn(k) the number of points in random mappings on {1,…, n} with distance k to cyclic points is asymptotically identically distributed with the number of cyclic points μn(0) if k = o(√n) by using the fact that (μn(k) - μn(0))√n 0 in probability. The main purpose of this paper is to provide a local limit theorem for the joint distribution of μn(k1), μn(k2). Furthermore, we prove a local version of Mutafchiev's result. All results are obtained by applying singularity analysis of multivariate generating functions. © 1995 Wiley Periodicals, Inc.

A “recursively decomposable network” can be partitioned into a finite number of subnetworks that are smaller “versions of itself,” where the subnetworks are themselves recursively decomposable. Several interesting notions of such networks emerge depending on the collections of parameters chosen to model the relative behavioral characteristics that make a subnetwork a version of another. Examples of such parameters are permutation time, bandwidth, latency, topology, wires, degree, and size. This paper introduces and studies the class of networks that are recursively decomposable relative to bandwidth limitations, and the subclass of “recurrent networks” that are recursively decomposable relative to topology limitations. We show that an N-node recursively decomposable into halves network with bandwidth-inefficiency function β(x) must be at least wires. This implies that the linear array, hypercube, and completely connected networks are all exactly optimal. The above lower bound is generalized to networks that are recursively decomposable, but not necessarily into halves. We show that the bound is tight up to a constant factor by exhibiting recurrent networks matching the above lower bounds. Our lower bound results both tighten and generalize a result of Meertens: no recurrent, fixed degree network can permute in O(log N) time. © 1996 John Wiley & Sons, Inc. ©1996 John Wiley & Sons, Inc.

Suppose that n tokens are arbitrarily placed on the n nodes of a graph. At each parallel step one token may be moved from each node to an adjacent node. An algorithm for the near‐perfect token distribution problem redistributes the tokens in a finite number of steps, so that, at the end, no more than O(1) tokens reside at each node. (In perfect distribution, at the end, exactly one token resides at each node.) In this paper we present a simple algorithm that works for all extrovert graphs, a new property which we define and study. In terms of connectivity requirements, extrovert graphs are roughly in‐between expanders and compressors. Our results lead to an optimal solution for the near‐perfect token distribution problem on almost all cubic graphs. The new solution is conceptually simpler than previous algorithms, and applies to graphs of minimum possible degree. © 1994 John Wiley & Sons, Inc.

In this paper we present a pathwise comparison theorem for jump processes governed by stochastic intensities and taking values in an arbitrary partially ordered Polish space. This generalizes recent results for the real-valued case. The proof given here is based on competing risk arguments rather than on thinning and allows to avoid additional domination conditions. For real valued processes we obtain an almost sure pathwise representation of the comparison result based on an i.i.d. sequence of (0, 1)-uniformly distributed random variables. For Markov chains our conditions coincide with the classical comparison conditions.

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Polya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.

The size Ramsey number r(G, H) of graphs G and H is the smallest integer r such that there is a graph F with r edges and if the edge set of F is red‐blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r(Tnd, Tnd) ⩽ c · d2 · n and c · n3 ⩽ r(Kn, Tnd) ⩽ c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc. © 1993 Wiley Periodicals, Inc.

Certain subclasses p(j, α), ℬp(j, α) and p,b(j, α) of multivalent functions in the unit disk are introduced. The object of the present paper is to derive some properties of functions belonging to the classes p(j, α), ℬp(j, α), or p,b(j, α). Further, generalizations of results for certain multivalent functions by M. NUNOKAWA, S. OWA and H. SAITOH [9], and by R. SINGH and S. SINGH [13] are shown.

The paper provides some central limit theorems for triangular arrays of Markov-connected random variables. It is assumed the Markov chain to satisfy condition (D1) which is an generalization of strong Doeblin's condition (Do). One result represents a central limit theorem without the assumption of finite variances.

A set of natural numbers is called an asymptotic basis of order k if every number (sufficiently large) can be expressed as a sum of k distinct numbers from the set. in this paper we prove that, for every fixed k, there exists an asymptotic basis of order k such that the number of representations of n is Θ(log n). © 1990 Wiley Periodicals, Inc.

The paper deals with strict solutions u(x,t) = u(x1,x2,x3,t) of an equation [Formula: see text] where Du is the set of four first derivatives of u. For given initial values u(x,0) = eF(x), ut(x,0) = eG(x), the life span T(e) is defined as the supremum of all t to which the local solution can be extended for all x. Blowup in finite time corresponds to T(e) < ∞. Examples show that this can occur for arbitrarily small e. On the other hand, T(e) must at least be very large for small e. By assuming that aik,F,G [unk] C∞, that aik(0) = 0, and that F,G have compact support, it is shown that [Formula: see text] for every N. This result had been established previously only for N < 4.

There are numerous physical situations in which a sequence of changes of state occurs, in an apparently random manner. Examples range from the reigning party in a multiparty political system to the sequence of tissue types in a linear tissue sample of a disorganized tissue mass. The question arises whether the two successive states are really correlated. The subject considered in this paper is the following: given the number of occurrences of each event in a sequence of trials, what is the probability distribution of the number of transitions. A weighted Markov transition probability is found. The associated generating function is evaluated explicitly by contour integration, and the desired probability distribution is extracted. Its long-chain asymptotic value is also obtained. (RWR)