|
In this talk, we show how with the machinery of distributed local algorithms, one can analyze a (non-distributed and global) Monte Carlo algorithm for the stochastic matching problem and prove that it obtains an almost maximum size matching.
Based on joint works with M. Hajiaghayi and M. Derakhshan (STOC'20, FOCS'20).
In this talk we discuss the challenges that arise due to bandwidth limitations. In particular, we show that even functions that admit $O(1)$-round algorithms in LOCAL, can be very hard in CONGEST.