Abstract: The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. In this talk, we will describe some results that illustrate surprising effectiveness of randomization in solving exact and approximate matching problems in small space or time. Specifically, the first part of the talk will focus on the problem of finding a perfect matching in a regular bipartite graph. We will show that sampling and random walks can be used to obtain surprisingly fast sublinear time exact algorithms for this problem. Our approach also yields an efficient algorithm for computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix as well as a near-linear time algorithm for rounding a fractional flow solution. In the second part of the talk, we will consider the problem of estimating the size of a maximum matching using small space in the streaming model. We show that if the edges of the graph are streamed in a random order, then poly-logarithmic space suffices to estimate the maximum matching size to within a poly-logarithmic factor. This is based on joint works with Ashish Goel, Michael Kapralov, and Madhu Sudan.
