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.
Relevant Paper (Fenner et al.): http://eccc.hpi-web.de/report/2015/177/