Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling

We study the problem of estimating the value of sums of the form $$S_p \triangleq \sum \left( {\begin{array}{c}x_i\\ p\end{array}}\right) $$Spźźxip when one has the ability to sample $$x_i \ge 0$$x...