[Colloquium] TTIC Colloquium: Sanjeev Khanna, University of Pennsylvania

[Liv Leader]

When:     Thursday, November 17 @ 11 a.m.

Where:   TTIC Conference Room #526, 6045 S. Kenwood Avenue, 5th Floor

Who:      Sanjeev Khanna, University of Pennsylvania

Title:       Perfect Matchings in Regular Bipartite Graphs

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.

Host: Julia Chuzhoy, cjulia at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu
Web-   www.ttic.edu