3 papers
cs.DS2026
Collision Detection is Instance ptimal Under the Birthday Threshold
Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň +1
Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the importan…
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.DS2023
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.…