Showing cs.DSShow all
3 papers · 1 filter
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…
cs.DS2024
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.…