4 papers
Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
Nathan White, Krish Singal
Quantization is a fundamental tool used to compress datasets, neural network weights, and memory usage in a range of computational tasks. Many downstream applications of vector qua…
On the size and complexity of scrambles
Seamus Connor, Steven DiSilvio, Sasha Kononova +2
The scramble number of a graph, a natural generalization of bramble number, is an invariant recently developed to study chip-firing games and graph gonality. We introduce the carto…
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…
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…