Sublinear Time Algorithms for Estimating Maximum Matching Size

Linear-time algorithms have long been the gold standard of algorithm design. But can we design algorithms that read only a small fraction of the input and run in sublinear time? In this talk, I will discuss such sublinear time algorithms for the problem of estimating the size of maximum matching in graphs. In particular, I will mention some recent upper as well as lower bounds for this problem.