A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams

Sanjeev Khanna, Ashwin Padaki, Krish Singal +1

We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stre…