11 citations · 11 across the 1 of their papers we have counts for
4 papers
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…
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
We give a general unified method that can be used for {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a s…
Testing Identity of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
We study the question of identity testing for structured distributions. More precisely, given samples from a {\em structured} distribution over and an explicit distributi…
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…