One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees @GoogleTechTalks
One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees  @GoogleTechTalks
Uploaded March 2024 | Updated November 2026, 6 days ago
A Google TechTalk, presented by D Ellis Hershkowitz, 2024-03-12
A Google Algorithms Seminar. ABSTRACT: One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies. This talk concerns universal Steiner trees (USTs). Informally, a UST is a single spanning tree that is a good approximation for every instance of Steiner tree. More formally, an α-approximate universal Steiner tree (UST) of a graph G for root vertex r is a spanning tree T such that, for any vertex subset S containing r, the cost of the minimal subtree of T connecting S is within an α factor of the cost of the minimum cost subgraph of G connecting S. α-approximate USTs immediately give α-approximations for well-studied variants of Steiner tree such as online or oblivious Steiner tree. Sub-linear-approximate USTs are known but neither the existence of nor poly-time algorithms for computing poly-logarithmic-approximate USTs were previously known.

In this talk, I will discuss the first construction of poly-logarithmic-approximate USTs which (nearly) exponentially improve the approximation guarantees of previous constructions and (nearly) match logarithmic lower bounds. The result is based on new constructions of poly-logarithmic-quality graph hierarchies called strong sparse partition hierarchies which may be interesting in their own right. Roughly, a strong sparse partition (i.e. each level of this hierarchy) is a vertex partition that provides deterministic guarantees on the number of parts balls of appropriate radii intersect.

Joint work with Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock and Rajmohan Rajaraman

Bio: Ellis Hershkowitz is an Assistant Professor in the Brown University Computer Science Department interested in graph, online and approximation algorithms as well as metric embeddings. He completed his PhD at Carnegie Mellon and did a postdoc at ETH Zurich.
One Tree to Rule Them All: Polylogarithmic Universal Steiner TreesUnderstanding Trade-offs Between Worst-case Differential Privacy Guarantees & Real Threat ModelsGraph Attention RetrospectiveMapping from Training Data to Predictions with Datamodels2023 Blockly Developer Summit DAY 1-14: BlocksCAD - Math + Coding + DesignCharles Hoskinson | CEO of Input Output Global | web3 talks | Jan 5th 2023 | MC: Marlon RuizFixed-point Error Bounds for Mean-payoff Markov Decision ProcessesRepresentational Strengths and Limitations of TransformersLow Cost High Power Membership Inference AttacksDisparate Privacy Risks from Medical AI - An Investigation into Patient-level Privacy RiskUnderstanding LLMs Like Physicists: Observation, Hypothesis, Experimentation, and PredictionDan Elitzer | Co-Founder of Nascent and IDEO CoLab Ventures | web3 talks | May 12th 2022
Google TechTalks |

One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER