1.5k citations · 1.6k across the 23 of their papers we have counts for
4 papers · 1 filter
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…
Multidimensional Binary Search for Contextual Decision-Making
Ilan Lobel, Renato Paes Leme, Adrian Vladu
We consider a multidimensional search problem that is motivated by questions in contextual decision-making, such as dynamic pricing and personalized medicine. Nature selects a stat…
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…
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Time
Michael B. Cohen, Aleksander Madry, Piotr Sankowski +1
In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching pr…