Sublinear time algorithms for better than 1/2 approximation algorithms for max-cut on expanders

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 in the setting of sublinear time algorithms for beating the trivial 1/2 approximation for max-cut on interesting families of graphs. In particular, the talk will cover how you can use random walks to also obtain insights about max-cut on 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. Based on joint work with Agastya Jha.