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-\epsilon$. It is shown that every randomized streaming algorithm for t…