Sublinear algorithms for testing monotone and unimodal distributions

By Tuğkan Batu, Ravi Kumar, Ronitt Rubinfeld. 2004

149 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Instance optimal learning of discrete distributions (2016, background): “…a long line of work considering distributional property testing, estimation, and learning questions from a worst case standpoint—typically parameterized via an upper bound on the support size of the distribution from which the samples are drawn (e.g. [8, 31, 5, 24, 10, 30, 36, 33, 32, 12, 34]).”
Testing Identity of Structured Distributions (2014, methodology): “In the context of property testing, Batu, Kumar, and Rubinfeld [BKR04] gave algorithms for the problem of identity testing of unimodal distributions with sample complexity O (log 3 n ) .”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, unknown): “Property Our results Previous bounds Uniformity Ω̃( √ n) Θ( √ n) [33, 44] Identity to p Ω(κ−1 p (1 − ε )), O (κ−1 p (1 − c · ε )) Ω( ‖p−max ε ‖2/3 ), O ( ‖p−max c′·ε ‖2/3 ) [55] Monotonicity Ω̃( √ n) Θ( √ n) [4, 11, 20] k-modal Ω̃( √ n) Ω̃(max( √ n, k )) [19] Log-concavity, Monotone Hazard Rate Ω̃( ”
Testing Properties of Collections of Distributions (2013, background): “2 Other related work Other works on testing and estimating properties of (single or pairs of) distributions include [8, 26, 13, 43, 2, 44, 6, 1, 5].”
Optimal Algorithms for Testing Closeness of Discrete Distributions (2013, background): “In addition to closeness testing, various properties of distributions have been considered, including independence [BFF01, Ona09], entropy [BDKR02], and the more general class of “symmetric” properties [Val08, VV11a, VV11b], monotonicity [BKR04], etc.”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “…body of work has focused on leveraging a priori structure of the underlying distributions to obtain significantly improved sample complexities Batu et al. (2004); Daskalakis et al. (2013); Diakonikolas et al. (2015a,b); Canonne et al. (2017a); Daskalakis and Pan (2017); Daskalakis et al.…”