This week

Which graphs $G$ admit a percolating phase (i.e. $p_c(G)<1$)? This seemingly simple question is one of the most fundamental ones in percolation theory. A famous argument due to Peierls implies that if the number of minimal cutsets of size $n$ from a vertex to infinity in the graph grows at most exponentially in $n$, then $p_c(G)<1$. Our first theorem establishes the converse of this statement. This implies, for instance, that if a (uniformly) percolating phase exists, then a "strongly percolating” one also does. In a second theorem, we show that if the simple random walk on the graph is uniformly transient, then the number of minimal cutsets is bounded exponentially (and in particular $p_c<1$). Both proofs rely on a probabilistic method that uses a random set to generate a random minimal cutset whose probability of taking any given value is lower bounded exponentially on its size.
Based on a joint work with Philip Easo and Vincent Tassion.

Speculative sampling is a popular technique for accelerating generation in Large Language Models whereby one samples candidate tokens using a fast draft model and accept/reject them based on the target model's distribution. While speculative sampling was previously limited to discrete sequences, we extend it to denoising diffusion models, which are state-of-the-art generative models for image, videos and protein generation. Our experiments demonstrate significant generation speedup on various denoising diffusion models, halving the number of function evaluations, while generating exact samples from the target model. We finally explain how this strategy can be also be used to accelerate simulation of Langevin diffusions.