Seminars & Colloquia
"New Directions for Random Walk on a Graph"
Wednesday January 21, 2015 10:30 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
Random walk on a graph is a beautiful and (viewed from today) classical subject with elegant theorems, multiple applications in the theory of computing, and a close connection to the theory of electrical networks. The subject seems to be livelier now than ever, with a surprising number of new results.
We will discuss recent progress in some new directions. In particular, how long can it take to visit every edge of a graph, or to visit every vertex a representative number of times? Can random walks be coupled so that they don't collide? Can moving targets be harder to hit than fixed targets? How long does it take to capture a random walker? Can random walk help a pursued rabbit?
Mentioned will be work by or with Omer Angel, Yakov Babichenko, Jian Ding, Oded Feldheim, Agelos Georgakopoulos, Ander Holroyd, Natasha Komarov, James Lee, James Martin, Yuval Peres, Ron Peretz, Perla Sousi, and David Wilson.
Peter Winkler is Professor of Mathematics and Computer Science, and Albert Bradley Third Century Professor in the Sciences, at Dartmouth College. A winner of the Mathematical Association of America's Lester R. Ford Award for mathematical exposition, he is the author of about 135 mathematical research papers and holds a dozen patents in computing, cryptology, holography, optical networking and marine navigation. His research is primarily in combinatorics, probability, and the theory of computing, with forays into statistical physics. Prof. Winkler has also authored two collections of mathematical puzzles, a portfolio of compositions for ragtime piano, and (just completed) a book on uses of cryptography in the game of bridge.
Host: Blair D. Sullivan, CSC