### DIMACS Theoretical Computer Science Seminar

Title: Perfect Matchings in Regular Bipartite Graphs

Speaker: **Sanjeev Khanna**, University of Pennsylvania

Date: Wednesday, March 30, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The problem of finding a perfect matching in a regular bipartite graph is a classical
problem with applications to edge-colorings, routing, and scheduling, and is closely
related to the Birkhoff-von Neumann decomposition of doubly stochastic matrices.
A sequence of improvements over the years have culminated in a linear-time algorithm
for this problem.

This talk considers the question if a perfect matching can be computed in sub-linear
time in a regular bipartite graph. We show that using randomization, one can obtain
surprisingly efficient sub-linear time algorithms for this problem. In contrast, we show
that no deterministic algorithm can do better than linear time.

This is based on joint work with Ashish Goel and Michael Kapralov at
Stanford University.