Seminars

View all Seminars  |  Download ICal for this event

Random Walks and Graph Property Testing

Series: Bangalore Theory Seminars

Speaker: Akash Kumar,Indian Institute of Technology Bombay

Date/Time: Apr 03 17:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
Random Walks on graphs reveal lots of interesting information about a graph and this information has been used to get a lot of algorithmic mileage in the classical literature on algorithms. It is perhaps not surprising that this primitive continues to be relevant even in the big data era as we deal with larger and larger graphs. In this talk, I will describe how random walks were put to use by algorithm designers even in the setting of sublinear time algorithms. The talk will cover how you can use random walks to gain insights about planar graphs and how you can use random walks to also obtain insights about expanding graphs and clusterable graphs. The talk will assume minimal background and it will attempt to present a standalone narrative which should be of interest to students and researchers in Spectral Methods. <br /><br />

Based on joint works with C. Seshadhri, Andrew Stolman, and Agastya Jha.<br /><br />
Microsoft teams link:
<br /><br />
Link
<br /><br />
We are grateful to the Kirani family for generously supporting the theory seminar series<br /><br />

Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar