The threshold for random (1,2)-QSAT (2009)
Creignou, Nadia, Daude, Herve, Egly, Uwe, Rossignol, Raphael
The QSAT problem is the quantified version of the SAT problem. We show the existence of a threshold effect for the phase transition associated with the satisfiability of random quantified extended...
Sharp threshold for percolation on expanders (2009)
Benjamini, Itai, Boucheron, Stephane, Lugosi, Gabor, Rossignol, Raphael
We study the appearance of the giant component in random subgraphs of a given finite graph G=(V,E) in which each edge is present independently with probability p. We show that if G is an expander...
Greedy Polyominoes and first-passage times on random Voronoi tilings (2008)
Pimentel, Leandro P. R., Rossignol, Raphael
Let N be distributed as a Poisson random set on R^d with intensity comparable to the Lebesgue measure. Consider the Voronoi tiling of R^d, (C_v)_{v\in N}, where C_v is composed by points x in R^d...
Threshold phenomena on product spaces: BKKKL revisited (once more) (2007)
We revisit the work of Bourgain, Kahn, Kalai, Katznelson and Linial (1992) -- referred to as ``BKKKL'' in the title -- about influences on Boolean functions in order to give a precise statement of...
Effective resistance on random electrical networks (2007)
Benaim, Michel, Benjamini, Itai, Rossignol, Raphael
This paper has been withdrawn. See v1 still available to understand the problem: Proposition 2.2 is false. The error in the proof is in claim (3). Then, the whole paper collapses. We do not have any...
Submean variance bound for effective resistance of random electric networks (2006)
Benjamini, Itai, Rossignol, Raphael
We study a model of random electric networks with Bernoulli resistances. In the case of the lattice Z^2, we show that the point-to-point effective resistance between 0 and a vertex v has a variance...
Benaim, Michel, Rossignol, Raphael
We provide a new exponential concentration inequality for First Passage Percolation valid for a wide class of edge times distributions. This improves and extends a result by Benjamini, Kalai and...
A modified Poincare inequality and its application to First Passage Percolation (2006)
Benaim, Michel, Rossignol, Raphael
We extend a Gaussian functional inequality to a countable product of Gaussian measures. This inequality improves on the classical Poincare inequality for Gaussian measures. As an application, we...