3 papers
cs.DC2025
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…
cs.DS2025
Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
Boaz Menuhin, Moni Naor
How can we generate a permutation of the numbers through so that it is hard to guess the next element given the history so far? The twist is that the generator of the permu…
cs.DS2024
From Donkeys to Kings in Tournaments
Amir Abboud, Tomer Grossman, Moni Naor +1
A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a \emph{king}. We study the complexity of finding king…