[Colloquium] Kulkarni/MS Presentation/May 20, 2008

[Margaret Jaffey]

This is an announcement of Raghav Kulkarni's MS Presentation.

----------------------------------------------------------------------------
Date:  Tuesday, May 20, 2008

Time:  1:30 p.m.

Place:  Ryerson 251

M.S. Candidate:  Raghav Kulkarni

M.S. Paper Title:  Deterministically Isolating a Perfect Matching in  
Bipartite Planar Graphs

Abstract:
"Matching" in a graph is simply a set of disjoint edges.  The end  
points of the edges in the matching are called "matched" vertices.   A  
"perfect matching" is a matching in which every vertex is matched.   
Deciding whether a graph has a perfect matching is a central problem  
in theoretical computer science. We will first briefly survey the  
history of the matching problem in sequential as well as parallel  
computation and then will focus on the "isolation" for matchings.

The Isolation Lemma due to Mulmuley, Vazirani and Vazirani (1987) is a  
simple but powerful tool which uses randomness to "isolate" a minimum  
weight subset in arbitrary family of subsets of a universe by  
assigning only O(log n) bits long weights. Mulmuley et al show that  
matching problem becomes as easy as matrix inversion after the  
isolation and thus admits an efficient randomized parallel algorithm.  
Allender, Reinhardt and Zhaou (1999) used the Isolation Lemma to give  
some non-uniform collapses among the complexity classes, e.g. NL is  
inside UL/poly.

One natural question is whether the randomness can be removed from the  
Isolation Lemma by assuming a  structured universe. Bourke, Tiwari and  
Vinodchandran (2007) showed that a deterministic isolation for  
directed paths in "grid graphs" is possible.  Their result, building  
on the work of Allender, Datta and Roy (2005) puts the directed planar  
reachability question in UL  whereas reachability in arbitrary  
directed graphs is NL-complete.

Motivated by their result, we consider the possibility of isolation  
for perfect matchings in planar graphs. In a joint work with Datta and  
Roy (2008) we show that there exists a Logspace computable function  
which assigns O(log n) bits long weights to the edges of a bipartite  
planar graph such that a minimum weight perfect matching in the graph  
becomes unique. As a consequence, we show that Bipartite Planar  
Perfect Matching is in SPL which improves the earlier bound of  
nonuniform SPL for the same problem. We will present this result in  
details.

To make things tight, recently (2008) we have showed that achieving  
such an efficient isolation in non-bipartite planar graphs would imply  
NL = UL..  Our techniques are simple and elementary.  All are welcome  
to attend the presentation.

Advisor:  Prof. Janos Simon

A draft copy of Raghav Kulkarni's MS paper is available in Ry 156.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=