Y. Peres

activity

20012013

most citedCritical random graphs: Diameter and mixing time

113 citations · 549 across the 71 of their papers we have counts for

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2011★ 3 cited

All-Pairs Shortest Paths in $O (n^{2})$ time with high probability

Yuval Peres, Dimitry Sotnikov, Benny Sudakov +1

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random…

math.CO2010

Finding Hidden Cliques in Linear Time with High Probability

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

We are given a graph $G$ with $n$ vertices, where a random subset of $k$ vertices has been made into a clique, and the remaining edges are chosen independently with probability $\t…

math.CO2009★ 5 cited

Anatomy of a young giant component in the random graph

Jian Ding, Jeong Han Kim, Eyal Lubetzky +1

We provide a complete description of the giant component of the Erdős-Rényi random graph $G (n, p)$ as soon as it emerges from the scaling window, i.e., for $p = (1 + ε) / n$ where $ε^3…

All-Pairs Shortest Paths in O(n2) time with high probability

Finding Hidden Cliques in Linear Time with High Probability

Anatomy of a young giant component in the random graph

All-Pairs Shortest Paths in $O (n^{2})$ time with high probability