Distribution Testing Meets Sum Estimation

Pinki Pradhan, Sampriti Roy

We study the problem of estimating the sum of $n$ elements, each with weight $w(i)$, in a structured universe. Our goal is to estimate $W={\sum }_{i=1}^{n}w(i)$ within a $(1\pm \epsilon )$…