Suppose you are given a function f\colon [n] \to [n] via (black-box) query access to the function. You are looking to find something local, like a collision (a pair x \neq y s.t.\ f(x)=f(y)). The question is whether knowing the `shape' of the function helps you or not (by shape ... more >>>