An upper bound on the space complexity of random formulae in resolution

Michele Zito

Displaying similar documents to “An upper bound on the space complexity of random formulae in resolution”

Consistent minimal displacement of branching random walks.

Fang, Ming, Zeitouni, Ofer (2010)

Electronic Communications in Probability [electronic only]

Similarity:

Generating functions and the satisfiability threshold.

Puyhaubert, Vincent (2004)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Smooth and sharp thresholds for random $k$ -XOR-CNF satisfiability

Nadia Creignou, Hervé Daudé (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The aim of this paper is to study the threshold behavior for the satisfiability property of a random $k$ -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with $k$ variables per equation. For $k \geq 3$ we show the existence of a sharp threshold for the satisfiability of a random $k$ -XOR-CNF formula, whereas there are smooth thresholds for $k = 1$ and $k = 2$ .

Bounding fastest mixing.

Roch, Sébastien (2005)

Electronic Communications in Probability [electronic only]

Similarity:

A note on quenched moderate deviations for Sinai’s random walk in random environment

Francis Comets, Serguei Popov (2004)

ESAIM: Probability and Statistics

Similarity:

We consider the continuous time, one-dimensional random walk in random environment in Sinai’s regime. We show that the probability for the particle to be, at time $t$ and in a typical environment, at a distance larger than $t^{a}$ ( $0 < a < 1$ ) from its initial position, is $exp {- Const \cdot t^{a} / [(1 - a) ln t] (1 + o (1))}$ .

Parallel probabilistic searching and sorting algorithms

Ivan Kramosil (1990)

Kybernetika

Similarity:

Survival time of random walk in random environment among soft obstacles.

Gantert, Nina, Popov, Serguei, Vachkovskaia, Marina (2009)

Electronic Journal of Probability [electronic only]

Similarity:

Selective encryption of Huffman compressed text

Miodrag Živković (2008)

Review of the National Center for Digitization

Similarity:

Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

Kunal Dutta, C.R. Subramanian (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance...