Abstract: Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem.

All known efficient matching algorithms for general graphs follow one of two approaches: given by Edmonds (1965) and Lovasz (1979). Our oracle-based algorithm follows a new approach and uses many of the ideas discovered in the last five years.

The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs.

This talk is heavily LP-based, but besides that it is fully self-contained.

Based on the following joint paper with Nima Anari:
https://arxiv.org/pdf/1901.10387.pdf

Bio: Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his Ph.D. from the University of California at Berkeley in 1983. He is currently Distinguished Professor at the University of California, Irvine.

Vazirani has made seminal contributions to the theory of algorithms, in particular to the classical maximum matching problem, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. His research on algorithms for the maximum matching problem spans four decades and on market equilibria spans two decades. His current interest is algorithms for matching markets.