Sublinear algorithms for testing monotone and unimodal distributions

DOI10.1145/1007352.1007414zbMath1192.68345OpenAlexW2129311580MaRDI QIDQ3580983

Ronitt Rubinfeld, Ravi Kumar, Tuğkan Batu

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007414

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (18)

Sampling Correctors ⋮ Hypothesis testing for high-dimensional multinomials: a selective review ⋮ Big Data on the Rise? ⋮ Linear time algorithms for Abelian group isomorphism and related problems ⋮ Testing shape restrictions of discrete distributions ⋮ On the power of conditional samples in distribution testing ⋮ Recovering Structured Probability Matrices ⋮ The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Testing permutation properties through subpermutations ⋮ Invariance in Property Testing ⋮ Testing Monotone Continuous Distributions on High-Dimensional Real Cubes ⋮ Improving and extending the testing of distributions for shape-restricted properties ⋮ Unnamed Item ⋮ Testing Probability Distributions using Conditional Samples ⋮ Unnamed Item

This page was built for publication: Sublinear algorithms for testing monotone and unimodal distributions