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 >>>

We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is k(n) Min-Entropic Optimal if for every distribution D with min-entropy at least k(n), its expected running time when its input is drawn ... more >>>

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>