13 citations · 18 across the 4 of their papers we have counts for
4 papers
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner +1
In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. I…
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry +2
We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow proble…
Electric routing and concurrent flow cutting
Jonathan Kelner, Petar Maymounkov
We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new r…
Faster generation of random spanning trees
Jonathan A. Kelner, Aleksander Madry
In this paper, we set forth a new algorithm for generating approximately uniformly random spanning trees in undirected graphs. We show how to sample from a distribution that is wit…