193 citations · 274 across the 24 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 3 cited
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, John Peebles +4
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of t…
cs.DS2016
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
Michael B. Cohen, Jon Kelner, John Peebles +3
In this paper, we provide faster algorithms for computing various fundamental quantities associated with random walks on a directed graph, including the stationary distribution, pe…
cs.CC2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
We prove that with high probability over the choice of a random graph from the Erdős-Rényi distribution , the -time degree Sum-of-Squares semidefinite p…