13 citations · 15 across the 3 of their papers we have counts for
3 papers
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…
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…
Using quantum oblivious transfer to cheat sensitive quantum bit commitment
Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry
It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independentl…