Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions

Adar Hadad, Moni Naor

Shared randomness is a valuable resource in distributed computing, allowing some form of coordination between processors without explicit communication. But what happens when the s…