Matching in NC and Local Events

Matching is in NC Matching theory is one of the richest gold mines of ideas and results in mathematics, computer science, and beyond. Recently, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf proved that bipartite matching is in NC. Namely, there is a polynomial-time algorithm of polylogarithmic depth that decides whether a bipartite graph has a perfect matching. This problem has long been regarded as a holy grail of complexity theory. Congratulations to Abhranil, Sumanta, Rohit, Roshan, and Thomas. The authors write in the abstract that “the techniques are based on the polynomial method, inspired by a construction of subspace designs by Guruswami and Kopparty (Combinatorica, 2016).” (See also this post about matching theory and VVV.) Local Mathematical Events Birthdays There is a great deal of mathematical activity around (sometimes with conflicting schedules), but not many international visitors. Last week there was a week-long school (Midrasha) on…