Near-Optimal Closeness Testing of Discrete Histogram Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

We investigate the problem of testing the equivalence between two discrete histograms. A {\em $k$-histogram} over $[n]$ is a probability distribution that is piecewise constant ove…