Sublinear Time Algorithms for Max-Cut Approximation on Expander Graphs

Explore a 32-minute lecture on sublinear time algorithms for approximating max-cut problems on expander graphs. Delve into how random walks on graphs reveal crucial information, particularly in the context of big data and large-scale graph analysis. Learn about the application of random walks in sublinear time algorithms to surpass the trivial 1/2 approximation for max-cut on expanding and clusterable graphs. Gain insights into the intersection of spectral methods and algorithmic design, with a focus on how these techniques can be leveraged to solve complex graph problems efficiently. Suitable for students and researchers interested in spectral methods, this talk by Akash Kumar from IIT Bombay requires minimal background knowledge and presents a standalone narrative on the subject.

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