One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies

Explore a groundbreaking Google TechTalk on universal Steiner trees (USTs) presented by D Ellis Hershkowitz. Delve into the first construction of poly-logarithmic-approximate USTs, which significantly improves previous approximation guarantees and nearly matches logarithmic lower bounds. Learn about strong sparse partition hierarchies, a new type of poly-logarithmic-quality graph hierarchy that provides deterministic guarantees on ball intersections. Discover the implications of this research for online and oblivious Steiner tree problems, and gain insights into graph algorithms, approximation techniques, and metric embeddings from an expert in the field.