[Colloquium] Tomorrow: Kulkarni/MS Presentation/May 20, 2008
Margaret Jaffey
margaret at cs.uchicago.edu
Mon May 19 11:06:48 CDT 2008
Just a reminder about Raghav Kulkarni's MS Presentation tomorrow
afternoon.
----------------------------------------------------------------------------
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list