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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20190712-L-Vaz
 irani.html
END:VEVENT
END:VCALENDAR