25 citations · 78 across the 26 of their papers we have counts for
4 papers · 1 filter
Linear Cover Time is Exponentially Unlikely
Itai Benjamini, Ori Gurel-Gurevich, Ben Morris
We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. More precisely, for every D and C, there exists…
Finding Hidden Cliques in Linear Time with High Probability
Yael Dekel, Ori Gurel-Gurevich, Yuval Peres
We are given a graph with vertices, where a random subset of vertices has been made into a clique, and the remaining edges are chosen independently with probability $\t…
Nonconcentration of return times
Ori Gurel-Gurevich, Asaf Nachmias
We show that the distribution of the first return time to the origin, v, of a simple random walk on an infinite recurrent graph is heavy tailed and nonconcentrated. More precis…
Optimal whitespace synchronization strategies
Yossi Azar, Ori Gurel-Gurevich, Eyal Lubetzky +1
The whitespace-discovery problem describes two parties, Alice and Bob, trying to establish a communication channel over one of a given large segment of whitespace channels. Subsets…