Streaming algorithms for products of probabilities

Markus Lohrey, Leon Rische, Louisa Seelbach Benkner +1

We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of $1-\hat{I}\mu$. It is shown that every randomized streaming algorithm for…