Showing 2025Show all
2 papers · 1 filter
cs.DS2025
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…
math.CO2025
Chip-Firing Games on Banana Trees
Marchelle Beougher, Nila Cibu, Kexin Ding +6
We study chip-firing games on multigraphs whose underlying simple graphs are trees, paths, and stars, denoted as banana trees, paths, and stars respectively. We present a polynomia…