BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Is matching in NC\, i.e.\, is there a deterministic fast para
llel algorithm for it? This has been an outstanding open question in TCS fo
r over three decades\, ever since the discovery of Random NC matching algor
ithms. Over the last five years\, the TCS community has launched a relentl
ess attack on this question\, leading to the discovery of numerous powerful
ideas. We give what appears to be the culmination of this line of work: An
NC algorithm for finding a minimum weight perfect matching in a general gr
aph with polynomially bounded edge weights\, provided it is given an oracle
for the decision problem. Consequently\, for settling the main open proble
m\, it suffices to obtain an NC algorithm for the decision problem. We be
lieve this new fact has qualitatively changed the nature of this open probl
em. Our result builds on the work of Anari and Vazirani (2018)\, which use
d planarity of the input graph critically\; in fact\, in three different wa
ys. Our main challenge was to adapt these steps to general graphs by approp
riately trading planarity with the use of the decision oracle. The latter w
as made possible by the use of several of the ideadiscovered over the last
five years. The difficulty of obtaining an NC perfect matching algorithm
led researchers to study matching vis-a-vis clever relaxations of the class
NC. In this vein\, Goldwasser and Grossman (2015) gave a pseudo-determinis
tic RNC algorithm for finding a perfect matching in a bipartite graph\, i.e
.\, an RNC algorithm with the additional requirement that on the same graph
\, it should return the same (i.e.\, unique) perfect matching for almost al
l choices of random bits. A corollary of our reduction is an analogous alg
orithm for general graphs. This talk is fully self-contained. Based on
the following joint paper with Nima Anari: https://arxiv.org/pdf/1901.1038
7.pdf
DTSTAMP:20190531T153700
DTSTART:20190712T101500
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Vortrag außer der Reihe: Vijay Vazirani (University of California\,
Irvine): Matching is as Easy as the Decision Problem\, in the NC Model Ach
tung: Dieser Vortrag ist an einem Freitag!
UID:99364940@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190712-L-Vazirani.html
END:VEVENT
END:VCALENDAR