Theory Seminar: Rajesh Jayaram
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]. However, for high dimensional spaces the best known approximation was Õ(log n), due to [Chen, Jayaram, Levi, Waingarten, STOC ‘22], and prior to that it was O(log^2 n) due to [Indyk, STOC ‘04] and [Andoni, Indyk, Krauthgamer, SODA ‘08]. In this talk, we describe the first algorithm which achieves a constant factor approximation in sublinear space. Specifically, for any ε > 0, the algorithm obtains a Õ(1/ε^2) approximation in n^{O(ε)} space. We show that this is tight up to a constant, by proving a Ω(sqrt(n)) lower bound for any algorithm that beats a 1.1 approximation.
Joint work with Xi Chen, Vincent Cohen-Addad, Amit Levi, and Erik Waingarten (to appear in STOC ‘23).
Paper: https://arxiv.org/abs/2212.06546