Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

On the Instance Optimality of Detecting Collisions and Subgraphs

Simons Institute via YouTube

Overview

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.

Syllabus

On the instance optimality of detecting collisions and subgraphs

Taught by

Simons Institute

Reviews

Start your review of On the Instance Optimality of Detecting Collisions and Subgraphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.