Abstract
Suppose you are given query access to a function f: [n] -> [n] and would like to find, say, a collision or a fixed point in f. Does knowing the "structure" of the function help with this task? (Here, by "knowing the structure" we mean that the algorithm is given an unlabeled copy of the function f.) What about subgraph detection problems in graphs? Does knowing the structure of a graph G help, say, in finding triangles?
The answer, as it turns out, strongly depends on the object we wish to find. There are three distinct classes of behavior. For some very simple objects, an algorithm that knows nothing about the input can actually be O(1)-competitive with one "knowing the structure" for all inputs. In most problems, including fixed point detection and triangle finding, the gap can be as large as polynomial in n. But most interestingly, there are two problems that seem to be "almost instance optimal": collision detection in functions and claw (3-star) detection in graphs. We conjecture both properties are Theta(log n)-optimal, prove the lower bound, and provide initial evidence toward a proof of a matching upper bound.
Joint work with Tomer Grossman and Moni Naor.