Graph Searching with Predictions
summary
Shows that with per-node distance hints an algorithm called TreeX finds a goal in a tree with total movement O(D + Δ·e), where D is true root–goal distance, Δ is max degree and e is number of wrong node predictions, nearly matching an Ω(Δ·e) lower bound. Key constructs are anchors and loads to locate erroneous regions, a doubling technique to bound backtracking, plus a tree-separator and voting scheme to handle unknown D. Results fail for weighted trees; extensions to general graphs remain open.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:19Problem Definition: Graph Searching
- 1:04Problem Definition: The Advice Setting
- 4:14The Exploration Problem: null prediction
- 8:16The Exploration Problem: Critical
- 9:07The Exploration Problem: Algorithm 1
- 9:52Algorithm Analysis -- Extra Exploration
- 10:25Algorithm Analysis -- Key Observations
- 10:54Algorithm Analysis -- Invariants
- 13:18The Exploration Problem: TreeX Alg Sketch
- 16:38The Exploration Problem: Conclusion
- 17:43Open Problems
related talks
52mNew Algorithms For The Graph Alignment Problem
29mSampling Algorithms for Combinatorial Pure Exploration
38mSome Easy Optimization Problems Have the Overlap-Gap Property
39mLocal Algorithms for Community Detection
14mBreaking the Reward Barrier: Accelerating Tree-of-Thought Reasoning via Speculative...
01h 01mNearest Neighbor Methods II
51mHow to Predict When Estimation is Hard: Algorithms for Learning on Graphs
40mDynamic programming - 101