\(L_p\) Sampling in Distributed Data Streams with Applications to Adversarial Robustness

In the distributed monitoring model, a data stream over a universe of size \(n\) is distributed over \(k\) servers, who must continuously provide certain statistics of the overall dataset, while minimizing communication with a central coordinator. In such settings, the ability to efficiently collect a random sample from the global stream is a powerful primitive, enabling a wide array of downstream tasks such as estimating frequency moments, detecting heavy hitters, or performing sparse recovery. Of particular interest is the task of producing a perfect \(L_p\) sample, which, given a frequency vector \(f \in \mathbb{R}^n\), outputs an index \(i\) with probability \(\frac{f_i^p}{\|f\|_p^p} + \frac{1}{\mathrm{poly}(n)}\). In this paper, we resolve the problem of perfect \(L_p\) sampling for all \(p \ge 1\) in the distributed monitoring model. Specifically, our algorithm runs in \(k^{p-1} \cdot \mathrm{polylog}(n)\) bits of communication, which is optimal up to polylogarithmic factors.