Campus Event Calendar
Event Entry
What and Who
Fine-Grained Complexity of Distance Oracles
Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 18 October 2022
13:00
45 Minutes
E1 4
007
Saarbrücken
Abstract
The classic Thorup-Zwick distance oracles allow to query k-approximate graph distances with O(1) query time and m^{1+O(1/k)} preprocessing time. We present fine-grained lower bounds showing that this tradeoff of approximation ratio, query time, and preprocessing time is near-optimal.
Specifically, we show that any k-approximate distance oracle has preprocessing time m^{1+Omega(1/k)} or query time m^{Omega(1/k)}, unless both the 3SUM and APSP hypotheses are false.
Joint work with Amir Abboud, Seri Khoury and Or Zamir.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk online but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de
Roohani Sharma, 10/14/2022 10:43 -- Created document.