Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications

Start Date: February 7, 2024
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Hengjie Zhang - Columbia University
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
Abstract:
We study graph spanners for point-set in the high-dimensional Euclidean space. On the one hand, we prove that spanners with stretch <\sqrt{2} and subquadratic size are not possible, even if we add Steiner points. On the other hand, if we add extra nodes to the graph (non-metric Steiner points), then we can obtain (1+\eps)-approximate spanners of subquadratic size. We show how to construct a spanner of size n^{2-\Omega(\eps^3)}, as well as a directed version of the spanner of size n^{2-\Omega(\eps^2)}.

We use our directed spanner to obtain an algorithm for computing (1+\eps)-approximation to Earth-Mover Distance (optimal transport) between two sets of size n in time n^{2-\Omega(\eps^2)}.

This is the joint work with Alexandr Andoni.

Events