Generating functions and the satisfiability threshold.

Puyhaubert, Vincent

Displaying similar documents to “Generating functions and the satisfiability threshold.”

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:

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

Michele Zito (2002)

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

Similarity:

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in $k$ -CNF on $n$ variables and $m = Δ n$ clauses is $O (n \cdot Δ^{- \frac{1}{k - 2}})$ .

A note on the non-colorability threshold of a random graph.

Kaporis, Alexis C., Kirousis, Lefteris M., Stamatiou, Yannis C. (2000)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps.

Löwe, Matthias, Matzinger, Heinrich, Merkl, Franz (2004)

Electronic Journal of Probability [electronic only]

Similarity:

Finding induced acyclic subgraphs in random digraphs.

Subramanian, C.R. (2003)

The Electronic Journal of Combinatorics [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))}$ .

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...