Abstract
Linear-time algorithms have long been the gold standard of algorithm design. But can we design algorithms that run even faster in time sublinear in the input size? In this talk, I will focus on such algorithms for estimating the size of maximum matching in graphs.
I will start by motivating the problem by showing how the recent progress on the sublinear time maximum matching problem has led to the resolution of a longstanding open problem in dynamic graphs. I will then present an overview of some existing algorithms for sublinear time matching.
Based mainly on