9 citations · 14 across the 4 of their papers we have counts for
4 papers
Collision-based Testers are Optimal for Uniformity and Closeness
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded -norm. Th…
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…
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…
Replacing Mark Bits with Randomness in Fibonacci Heaps
Jerry Li, John Peebles
A Fibonacci heap is a deterministic data structure implementing a priority queue with optimal amortized operation costs. An unfortunate aspect of Fibonacci heaps is that they must…