摘要:

AbstractWe consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function onnvariables, setting all but a randomly chosen ϵnvariables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω(n1.5) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of ΩC(n2.5/logO(1)(n)) for a function inP. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most anO(ϵγ) franction of its original complexity, forThis allows us to give an improved lower bound of Ω(n2.556…) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wi

ISSN:1042-9832    

DOI:10.1002/rsa.3240040202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractIt is shown that a random restriction leaving only a fraction ϵ of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor ofO(E(5−√2)/2) =O(ϵ1.63). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long‐standing result ofO(ϵ1.5) by Subbotovskaya and a recent improvement toO(ϵ(21−√73)/8) =O(ϵ1.55) by Nisan and Impagliazzo. The New exponent yields an increased lower bound ofn(7−√3)/2−o(1)= Ω(n2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP.

ISSN:1042-9832    

DOI:10.1002/rsa.3240040203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThis 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 Pólya 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

ISSN:1042-9832    

DOI:10.1002/rsa.3240040204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe consider a continuum percolation model in ℝd,d⩾ 1 in which any two points of a stationary point process are connected with a probability which decays exponentially in the distance between the points. We give sufficient conditions for the (non)‐existence of a phase transition. We also give examples of processes which show that it is impossible to write down a theorem which relates the critical parameter value of a process to its density. Finally, we show that uniqueness of the infinite cluster is still valid in this general setting. © 1993 John Wiley&Son

ISSN:1042-9832    

DOI:10.1002/rsa.3240040205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThe study and comparison of strings of symbols from a finite or an infinite alphabet is relevant to various areas of science, notably molecular biology, speech recognition, and computer science. In particular, the problem of finding the minimum “distance” between two strings (in general, two blocks of data) is of a practical importance. In this article we investigate the (string) pattern matching problem in a probabilistic framework, namely, it is assumed that both strings form an independent sequences of i.i.d. symbols. Given a text stringaof lengthnand a pattern stringbof lengthm, letMm,nbe the maximum number of matches betweenband allm‐substrings ofa. Our main probabilistic result shows that for a wide range of input parameters in probability (pr.) providedm, n→∞ such that logn=o(m), wherePis the probability of a match between any two symbols of these strings, andTis the probability of a match between two positions in the text string and a given position of the pattern string. We also prove thatMm,n/m→P almost surely(a.s.) for logn=o(m). © 1993 John Wil

ISSN:1042-9832    

DOI:10.1002/rsa.3240040206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractLetGn= (Vn, En) be the random subgraph of then‐cube graphQnproduced as follows:Vnis randomly sampled from the vertex set ofQnso thatE{x∈Vn} =pvindependently for each vertexx∈Qn. ThenEnis randomly sampled from the set of edges induced byVninQnso thatP{(x, y) ∈En} =peindependently for each induced edge (x, y). LetPvandpebe fixed probabilities such that 0

ISSN:1042-9832    

DOI:10.1002/rsa.3240040207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240040201

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY