April 7, 2023
Our speaker for the Theory Seminar on 4/7 will be Rajesh Jayaram of Google Research. As usual, the talk will take place at 1pm in Levine 307.
Title: Streaming Euclidean MST to a Constant Factor
Abstract: We consider the problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) of an n-point set X in R^d, where the points in X are presented in a stream. In low dimensions, (1+ε) approximations are possible in sublinear (in n) space [Frahling, Indyk, Sohler, SoCG ‘05].