Embeddings and labeling schemes for A*

on YouTube ↗19m

" summary

Proves nearly tight tradeoffs between heuristic complexity and A scans: for Lp embeddings with dimension D < N/log N A scans Ω(N) on average; for L∞ or label-length L < N^α A scans Ω(N^{1−α}). Constructions use low-dimension embeddings, equilateral-set distortion plus amplifier gadgets, and an indexing communication lower bound. Matching upper bounds show beacon sets of size N^α yield average additive overhead N^{1−α} (with arbitrary tie-breaking) and a label construction using Euler-tour tie-breaking encoding* achieves the same under unique shortest paths.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 0:40Motivation
3. 1:13A* algorithm
4. 2:00Example
5. 3:36A* Propositions
6. 5:14Metric
7. 6:51Heuristic types
8. 8:52Main results
9. 9:20Lower bound for norm heuristics
10. 11:21Stronger lower bound for I. norm heuristi
11. 11:59Stronger lower bound for 1. norm heuristi
12. 13:30Lower bound for labeling heuristics
13. 14:56Upper bounds
14. 18:14Conclusion