How Fast Can You Estimate the Volume of a Union?

In 1985, Karp and Luby introduced a model that can handle inputs of different natures. They (and later with Madras) also designed an O(n ɛ^{-2}) algorithm for Union Volume Estimation in this model. The algorithm remains the state of the art, even for the special case where X_1, ..., X_n are boxes. Is it actually optimal? And even more, is it optimal when the inputs are boxes?

In this talk, I will explain the model and the ideas behind their algorithm. Then I will present our answers to the questions: (1) Yes, the algorithm is indeed optimal, due to communication complexity reason; (2) No, it can be improved when the inputs are boxes, by exploiting the geometry.

The talk is based on joint work with Karl Bringmann, Kasper Green Larsen, André Nusser and Eva Rotenberg.