4 papers · 1 filter
Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling
Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan
We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to t…
Improved Algorithms for Clustering with Noisy Distance Oracles
Pinki Pradhan, Anup Bhattacharya, Ragesh Jaiswal
Bateni et al. has recently introduced the weak-strong distance oracle model to study clustering problems in settings with limited distance information. Given query access to the st…
Distribution Testing Meets Sum Estimation
Pinki Pradhan, Sampriti Roy
We study the problem of estimating the sum of elements, each with weight , in a structured universe. Our goal is to estimate within a …
Improved Sublinear-time Moment Estimation using Weighted Sampling
Anup Bhattacharya, Pinki Pradhan
In this work we study the {\it moment estimation} problem using weighted sampling. Given sample access to a set with weighted elements, and a parameter , we estimate t…