Electrical Networks and Random Walks
April 18th, 2007 by WaltPeople always post interesting links in the comments to Scott Aaronson’s weblog. For example, the other day Paul Beame posted two links that explain the connections between random walks on graphs and electrical networks. One is a complete book on the subject by Doyle and Snell. The other is an article by Chandra, Raghavan, Ruzzo, Smolensky, and Tiwari that further develops the theory.
April 22nd, 2007 at 9:30 am
The article is extremely fine, both entertaining, and linking two previously different concepts. It also allows improved bounds on known results, and is robust — able to work with nearly-regular structures, whose imperfection has negligible effect on results, but prevents traditional analytical methods.