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.

"