On the Instance Optimality of Detecting Collisions and Subgraphs

Explore the intricacies of detecting collisions and subgraphs in this 26-minute lecture by Omri Ben Eliezer from the Massachusetts Institute of Technology. Delve into the question of whether knowing the structure of a function or graph aids in finding collisions, fixed points, or specific subgraphs. Discover three distinct classes of behavior in object detection, ranging from O(1)-competitive algorithms to those with polynomial gaps. Examine the fascinating cases of collision detection in functions and claw detection in graphs, which are conjectured to be Theta(log n)-optimal. Learn about the proven lower bounds and initial evidence supporting matching upper bounds. Gain insights from this joint work with Tomer Grossman and Moni Naor, presented as part of the Workshop on Local Algorithms (WoLA) at the Simons Institute.

On the instance optimality of detecting collisions and subgraphs