Sublinear Time Algorithms for Maximum Matching

Linear-time algorithms have long been the gold standard of algorithm design. But can we design algorithms that run even faster, i.e., in time *sublinear* in the input size? In this talk, I will show how this is possible for the fundamental maximum matching problem.