Tight Space Lower Bounds for Fault-Tolerant Approximate Diameter and Radius
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.