30 citations · 38 across the 16 of their papers we have counts for
24 papers
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…
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…
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…
On the instance optimality of detecting collisions and subgraphs
Omri Ben-Eliezer, Tomer Grossman, Moni Naor
Suppose you are given a function via (black-box) query access to the function. You are looking to find something local, like a collision (a pair s.…
Adjacency Sketches in Adversarial Environments
Moni Naor, Eugene Pekel
An adjacency sketching or implicit labeling scheme for a family of graphs is a method that defines for any vertex an assignment of labels to each vertex…
Private Everlasting Prediction
Moni Naor, Kobbi Nissim, Uri Stemmer +1
A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privac…