Colloquium: Power and Limits in Algorithm Design

Structures in Algorithm Design: Power and Limits Talk by Hung Le Similar to talk Distance Sparsification in Bounded Geometry Bounded Geometry Bounded Geometry Doubling space for peer-to-peer networks. Finite metric space. identificiation, symmetry, triangle inequality. Doubling dimension. Think of metric space as edge-weighted graph (by distance). Doubling Spaces Distance Sparsification Sparsification Question: Trade-off between stretch and lightness. Application of Spanners Routing ML Distributed Systems Construct Minimum Spanning Tree Kruskal algorithm Add t stretch factor for the determination of adding edge.