Tight Space Lower Bounds for Fault-Tolerant Approximate Diameter and Radius

Data dell'evento: 
Thursday, 22 March, 2018 - 12:00
Aula B203 - DIAG - Via Ariosto 25
Omer Gold (Tel-Aviv University)

We prove information theoretic lower bounds for the space complexity of fault-tolerant c-approximate diameter and radius data structures (oracles). Our bounds for the diameter oracle are tight for any approximation factor c < 3/2, and in the single-failure model our bounds are also tight for any c >= 2. For c = 3/2, we show a single-failure fault-tolerant oracle that uses significantly less space than the tight lower bound of the c < 3/2 case. For the radius oracle our bounds are tight for any approximation factor in the single-failure model.

Our results almost completely settle the space complexity of fault-tolerant approximate diameter and radius oracles in the single-failure model, leaving open only what happens in the diameter oracle when the approximation factor is 3/2 =< c < 2. Our results also imply strong space complexity separation between the diameter and radius oracles.

Joint work with Sarel Cohen.


© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma