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 continue to discuss algorithms for estimating the size of maximum matching. However, I will focus on lower bounds this time. Specifically, I will provide an overview of a recent technique based on correlation decay that leads to super-linear (in the number of nodes) lower bounds for estimating the size of maximum matching provided that the desired approximation is larger than 2/3.
Based on joint works with Mohammad Roghani and Aviad Rubinstein.