22 citations · 112 across the 37 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
math.PR2022
Speeding up random walk mixing by starting from a uniform vertex
Alberto Espuny Díaz, Patrick Morris, Guillem Perarnau +1
The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initia…
cs.FL2022
Short Synchronizing Words for Random Automata
Guillaume Chapuy, Guillem Perarnau
We prove that a uniformly random automaton with states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to s…
math.PR2022
Percolation on dense random graphs with given degrees
Lyuben Lichev, Dieter Mitsche, Guillem Perarnau
In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a…