Loading Events

« All Events

  • This event has passed.

Fishbowl teleseminar: Three Random Walks that Surprise

September 19, 2013 @ 3:00 pm - 5:00 pm

Prof. Ashish Goel
Associate Professor of Management Science and Engineering and (by courtesy) Computer Science
Stanford University



We will describe three simple random walks in graphs, each arising in a different application domain, and each with surprising algorithmic implications.


The first walk finds an augmenting path in regular bipartite graphs, and leads to an O(n log n) algorithm for finding a perfect matching in such graphs, where n is the number of nodes. This is surprising because the running time does not depend on the number of edges in the graph, and is sub-linear even for moderately dense graphs. The same random walk extends to finding a permutation in the support of a doubly-stochastic matrix.


The second walk simulates the PageRank process in evolving graphs. We show (under a weak assumption on the arrival order of edges) the surprising result that the amortized amount of work required to update the PageRank of all nodes in the graph after every edge arrival goes to 0, and the total work over all m edge arrivals is less than m for even moderately dense graphs.


The third random walk describes transactions in credit networks, a distributed model of currency, motivated by applications to reputation and trust systems. Payments are made by passing IOUs along chains of trusted nodes. The vector of residual trust between any pair of nodes forms a state in a Markov Chain. We show that under symmetric transaction rates, every (appropriately defined) equivalence class of states is equally likely. This allows us to compare transaction failure rates under our distributed currency to an equivalent centralized system. We show the surprising result that for many classes of underlying trust topologies, the distributed and centralized currency have comparable failure rates, and hence, the distributed currency has the same liquidity as the centralized system.



Ashish Goel is an Associate Professor of Management Science and Engineering and (by courtesy) Computer Science at Stanford University, and a member of Stanford’s Institute for Computational and Mathematical Engineering. He received his PhD in Computer Science from Stanford in 1999, and was an Assistant Professor of Computer Science at the University of Southern California from 1999 to 2002.


His research interests lie in the design, analysis, and applications of algorithms; current application areas of interest include social networks, Internet commerce, and large scale data processing. Professor Goel is a recipient of an Alfred P. Sloan faculty fellowship (2004-06), a Terman faculty fellowship from Stanford, an NSF Career Award (2002-07), and a Rajeev Motwani mentorship award (2010). He was a co-author on the paper that won the best paper award at WWW 2009.


Professor Goel also serves on the technical advisory board of Twitter, Inc.


September 19, 2013
3:00 pm - 5:00 pm