A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

Yi-Jun Chang, Kushagra Chatterjee

We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs $G=(V,E)$ using only a few shared random bits. Specifically, in the $\c…