11 citations · 11 across the 1 of their papers we have counts for
2 papers
cs.DS2017★ 11 cited
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 -histogram} over is a probability distribution that is piecewise constant ove…
cs.CC2012
Amortized communication complexity of an equality predicate
Vladimir Nikishkin
We study the communication complexity of a direct sum of independent copies of the equality predicate. We prove that the probabilistic communication complexity of this problem is e…