Title: Parallel algorithms for perfect matchings
| Speaker: | Nathan Lindzey |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
In
1979,
Lovasz
showed
that
one
can
decide
if
a
graph
has
a
perfect
matching
efficiently
in
parallel
if
given
access
to
random
bits.
A
few
years
later,
Karp
et
al.
and
Mulmuley
et
al.
showed
that
one
can
actually
construct
a
perfect
matching
efficiently
in
parallel
if
given
access
to
random
bits.
It
is
natural
to
wonder
whether
randomness
is
necessary
to
decide
if
a
graph
has
a
perfect
matching
efficiently
in
parallel.
This
is
the
outstanding
open
question
of
the
area,
and
in
accordance
with
certain
dogma
of
complexity
theory,
the
prevailing
belief
is
that
random
bits
are
not
needed.
The
recent
work
of
Fenner
et
al.
is
a
testament
to
this
conjecture,
as
they
give
a
deterministic
algorithm
that
constructs
a
perfect
matching
of
a
bipartite
graph
"almost"
efficiently
in
parallel.
We give an overview of this work along with a few other noteworthy results. We conclude with some plausible directions for future research in the area.
Door will open at 4:30pm. As usual we will have 15 mins for socializing and for eating pizza before the talk starts (at 4:45pm sharp).
For more information about our reading group, please visit our webpage http://www.math.uwaterloo.ca/ hwolkowi/reading.htm