On the instance optimality of detecting collisions and subgraphs
summary
Characterizes when knowing an unlabeled copy of the input helps: a trichotomy shows very simple targets are O(1) instance optimal, most targets incur a polynomial gap, and two middle cases—function collisions and graph claws—exhibit only a log n gap. The talk proves a lower bound of Theta(log n) hardness and gives evidence toward a matching upper bound via a bucketing algorithm that runs ~log n parallel random walks of lengths 2^i and an analysis tailored to the unlabeled-query model.
AI-written summary · about