Soheil Behnezhad, Northeastern University

Abstract

Over the past two decades there has been a growing interest in estimating various graph parameters, such as the size of maximum matching (MM) and minimum vertex cover (MVC), in time that is sublinear in the input size. In this talk, I will start by discussing a powerful method of the literature for obtaining such sublinear time algorithms based on the randomized greedy maximal matching (RGMM) algorithm. I will then present an improved and near-tight analysis of the “average query complexity” of RGMM, leading to algorithms for estimating the size of MM and MVC up to a factor of (almost) two in time near-linear in the number of vertices. The new algorithms turn out to be information theoretically time-optimal (up to logarithmic factors), culminating a long line of work on these two problems.
Based on https://arxiv.org/abs/2106.02942 (to appear in FOCS'21).

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar